문제

• 
• 시간 제한: 1초
• 메모리 제한: 128MB

Problem Analysis

특정 칸에서 순회를 시작하여 방문하게 되는 모든 칸들은 같은 구역이고, 방문하지 않으면 다른 구역이다. 순회를 했을 때 서로 접근할 수 없는 구역의 개수를 세면 된다. 이때, 넓이든 깊이든 모든 칸을 순회만 할 수 있으면 되기 때문에, BFS든 DFS든 상관없다.

Algorithm

1. 방문하지 않은 칸을 Queue에 넣는다.
2. Queue를 통해 BFS를 시작한다.
3. Queue가 끝나면 1번으로 돌아가, 방문하지 않은 칸이 없을 때까지 반복한다.

1-2번이 반복하는 수가 곧 구역의 수이다.

Data Structure

• Queue
• painting[N][N]
• visited[N][N]

결과

Other