지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.
그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보
빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.
그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.
그림 2
그림 3
한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
입력
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
출력
첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.
풀이
public class Main {
static int N, M, count;
static int[][] field;
static boolean[][] visited;
static int[] dx = {0,0,-1,1};
static int[] dy = {1,-1,0,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
field = new int[N][M];
for (int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
for (int j=0; j<M; j++){
field[i][j] = Integer.parseInt(st.nextToken());
}
}
int year = 0;
while (true){
visited = new boolean[N][M];
count = 0;
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
if (!visited[i][j] && field[i][j] > 0){
DFS(i, j);
count++;
}
}
}
if (count == 0){
year = 0;
break;
} else if (count >= 2){
break;
}
BFS();
year++;
}
System.out.println(year);
}
static void DFS(int x, int y){
visited[x][y] = true;
for (int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >=0 && ny >= 0 && nx < N && ny < M){
if (!visited[nx][ny] && field[nx][ny] > 0){
DFS(nx, ny);
}
}
}
}
static void BFS(){
Queue<int[]> queue = new LinkedList<>();
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
if (field[i][j] > 0){
queue.offer(new int[]{i, j});
}
}
}
while (!queue.isEmpty()){
int[] point = queue.poll();
int count = 0;
for (int i=0; i<4; i++){
int nx = point[0] + dx[i];
int ny = point[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M){
if (!visited[nx][ny] && field[nx][ny] == 0){
count++;
}
}
}
if (field[point[0]][point[1]] >= count){
field[point[0]][point[1]] -= count;
} else {
field[point[0]][point[1]] = 0;
}
}
}
}
해설
BFS와 DFS, 그리고 분기처리까지 잘 할수 있냐를 물어보는 문제였다.
큰 틀은 다음과 같다.
- DFS로 돌면서 빙산 개수 체크하기
- BFS로 1년씩 빙산 녹이기
- 주의할 점은 방문 배열을 잘 이용해서 지금 녹아 없어지는 빙하가 다른 빙하에 영향을 주면 안됨
- 빙산의 개수 체크하기
- 빙산이 한 번에 다 녹아버린다면(DFS의 결과가 0이라면) 0을 출력
- 이외에는 지난 연도 출력
static int N, M, count;
static int[][] field;
static boolean[][] visited;
static int[] dx = {0,0,-1,1};
static int[] dy = {1,-1,0,0};
사전에 선언해줄 변수들은 가로 세로를 나타내는 N, M, 그리고 빙산의 개수를 카운팅해줄 count라는 변수를 선언한다.
field와 이번에 중요한 역할을 할 visited 배열도 선언한다.
마지막으로, 빙산의 가로, 세로에 영향을 끼치므로 델타배열을 선언해준다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
field = new int[N][M];
for (int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
for (int j=0; j<M; j++){
field[i][j] = Integer.parseInt(st.nextToken());
}
}
int year = 0;
while (true){
visited = new boolean[N][M];
count = 0;
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
if (!visited[i][j] && field[i][j] > 0){
DFS(i, j);
count++;
}
}
}
if (count == 0){
year = 0;
break;
} else if (count >= 2){
break;
}
BFS();
year++;
}
System.out.println(year);
}
메인 함수부터는, 위에 써놓은 틀대로 따라가면 된다.
먼저 field를 채우고, year를 선언해주고 while문 안으로 들어간다.
여기서 중요한게 매 해마다 빙산의 개수가 변할 수 있으므로 visited배열을 꼭 초기화해준다.
물론 DFS함수 내부에서 visited배열을 true/false로 조작해도 되지만, 알아보기 쉽게 밖에서 초기화해준다.
그리고 DFS함수가 몇 번 실행됐는지(빙산이 몇개인지)를 count변수로 체크하고,
count변수에 따라 분기처리를 해서 1이 아니라면 break해서 빠져나간다.
만약 count==1이라면 빙산이 아직 덜 녹은 것이므로
BFS로 한번 더 녹이고, year를 후위덧셈 해준다.
static void DFS(int x, int y){
visited[x][y] = true;
for (int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >=0 && ny >= 0 && nx < N && ny < M){
if (!visited[nx][ny] && field[nx][ny] > 0){
DFS(nx, ny);
}
}
}
}
DFS함수 같은 경우는 단순한 로직을 띈다. 그냥 방문 배열과 조건에 맞춰서 체크만 해주면 되는 로직을 탄다.
static void BFS(){
Queue<int[]> queue = new LinkedList<>();
for (int i=0; i<N; i++){
for (int j=0; j<M; j++){
if (field[i][j] > 0){
queue.offer(new int[]{i, j});
}
}
}
while (!queue.isEmpty()){
int[] point = queue.poll();
int count = 0;
for (int i=0; i<4; i++){
int nx = point[0] + dx[i];
int ny = point[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M){
if (!visited[nx][ny] && field[nx][ny] == 0){
count++;
}
}
}
if (field[point[0]][point[1]] >= count){
field[point[0]][point[1]] -= count;
} else {
field[point[0]][point[1]] = 0;
}
}
}
마지막으로 제일 애먹었던 BFS 로직이다.
시작점을 어디서 추가해야 하나 엄청 고민했는데, 결국 배열을 돌면서 빙산이 있는 필드를 큐에 담고 시작하는게 정답이었다.
while문을 들어올때 처음으로 visited 배열을 초기화하고 들어와서 DFS를 진행했으므로,
지금은 visited에 빙산만 체크되어 있을 것이다.
왜 visited를 사용해야 하는지에 대한 이유는 다음과 같다.
0 0 0 0
0 3 4 0
0 0 0 0
이라는 배열이 있다고 했을 때, 1년이 지난다면 상식적으로
0 0 0 0
0 0 1 0
0 0 0 0
이 되어야 한다.
그러나 방문 배열이 없을 경우, 배열을 돌면서 차례로 큐에 [1,1], [1,2]가 들어가기 때문에,
[1,1]이 먼저 0으로 녹아 없어지면서 [1,2] 주위에는 빙산이 4개가 되어버린다.
결국
0 0 0 0
0 0 0 0
0 0 0 0
이런 형태를 띄게 된다.
그리고나서 count(사실은 변수를 다르게 하는게 좋다. 나는 실수로 지역변수로 똑같이 선언해버렸다)를 확인하고, 개수대로 빼주되, 음수가 나올 경우 0으로 바꿔주는 로직만 있으면 된다.
풀고 보니 로직 자체가 어려운 문제는 아니였지만, 처음 풀 때는 와 이거 어떻게 해야하지? 라는 생각을 가득 했던것 같다.
하지만 DFS+BFS를 둘 다 이용하는 중요하고 좋은 문제였다.
