Personal IT Notes

풀이 이 문제는 BFS탐색과 비트마스킹을 실행해줘야하는 문제다. 1. bfs탐색을 돌면서벽이 아닌 경우를 체크하고 방을 움직여야한다. 그럴 수 있는 조건은(move & (1

풀이 1. bfs탐색을 통해서 해결하는데 bfs함수를 돌리기 전에 미리 que에 물의 좌표랑 고슴도치의 좌표를 넣어야 한다. why?) 만약 물이 존재하지 않는 경우 물의 좌표를 넣어둘려고 초기화된 0,0의 값이 que에 들어가서 잘못된 값이 출력 된다. 2. 고슴도치는 물이 확산될 위치를 예상하고 움직이면 안된다. -> bfs함수 내에서 물을 먼저 확산시키고 나서 고슴도치가 이동해야한다. 3. 만약 고슴도치를 확산했는데 큐에 새로 확산할 좌표가 안들어왔다면, 더이상 다음부턴 못 움직인다는것을 의미한다. 즉, bfs탐색을 끝낸다. 코드

풀이 8방탐색을 통해 풀수 있는 문제다. 1.이중for문을 이용하여 1의 값이 있는 좌표에서 bfs탐색을 한다. 2. 한번 bfs탐색을 통해 8방으로 최대한 이동할 수 있는 공간을 탐색 후 탐색이 끝나면 그때 섬의 개수가 1씩 증가한다. 3. 방문배열을 만들어서 한번 방문한 좌표는 다시는 방문하지 않도록 설정한다. 코드

풀이 이 문제는 분할 정복을 이용하여 해결할 수 있습니다. 1. 첫 크기는 배열의 사이즈로 설정하고 재귀를 돌립니다. 2. 범위 내에 전부 1이거나 0이 아니면 다시 분할하여 재귀를 돌리게 됩니다. 3. 범위를 4분할하여 다시 재귀를 돌리면서 2번의 조건이 만족할때까지 반복합니다. 코드