목록백준 (8)
시간이 NullNull
장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 처음에 그 높이만 물에 잠기는 줄 알고 많이 틀렸었다. 문제를 잘 읽도록 하자... ( 오랜만에 알고리즘 하니까 재미는 있지만 어렵네요 ㅠ ) 1. 생각해보면 비가 내리지 않았을 경우? 혹은 최소 높이보다 비가 작게 내렸을 경우? 안전 영역의 최소 값은 1이 된다. ( Key point) ( 내 생각에는 문제의 오류라고 생각한다. 최소 높이가 1이라면 비가 내리지 않았다가 된다. ) ( 이 생각 때문에 몇번 틀렸다. ) 2. 비는 최소 높이 부터 최고 높이의 - 1 까지만 내리는 것을 확인하면 된다. ( 최고 높이 이상으로 내릴 경우 어차피 안전영역은 0 이다. 최소 안전 영역이 1이 되는 것을 위배한다. ) 3. ..
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 이 문제의 포인트는 위의 문장이라고 생각이 들었다. 그렇다면 같은 시간에는 물이 먼저 이동하고 그 뒤에 고슴도치가 이동한다고 다르게 생각할 수도 있다고 생각하였고 물이 먼저 움직인 후에 고슴도치가 움직이면 되겠다고 생각하였다. 1. 한 사이클당 물이 한번 번진다.2. 한 사이클당 고슴도치가 한번 움직인다.2-1. 고슴도치가 못 움직이게 되면( 빠지는 경우 포함 ) 더이상 Queue에 다시 넣을 노드가 사라지게 됨으로 종료3. 도착하면 그때 몇 사이클 움직이게 되었는지 파악하여 결과값 출력 물의 좌표와 고슴도치의 좌표를 각각 Queue..
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.빈 칸의 개수는 3개 이상이다. 라는 문구가 가장 먼저 눈에 띄었고 N이 8이하 벽은 3개 라는 것에 착안점을 두어 3중 for문으로 벽을 세울 인덱스를 정한뒤 바이러스가 퍼지도록 bfs를 하여 그 때 남은 0의 갯수를 세어 확인하였다. 3중 for문을 작성할때 ( 3개의 점을 고를때 ) 같은 점을 찍지 않도록 그리고 0인점만 골라 벽을 세울 수 있도록 다음과 같이 작성하였다.첫번째 for문 기준으로 idx / M(가로크기) 는 일반적인 배열의 i ..