[백준] 14497 주난의 난(難)

문제 링크:

14497번: 주난의 난(難)

 

 

난이도: 골드 4

 

 

문제:

주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다.

‘쿵... 쿵...’

주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 N×M크기의 학교 교실 어딘가에서 뛰기 시작했다. 주난이의 파동은 상하좌우 4방향으로 친구들을 쓰러뜨릴(?) 때 까지 계속해서 퍼져나간다. 다르게 표현해서, 한 번의 점프는 한 겹의 친구들을 쓰러뜨린다. 다음의 예를 보자.

1 # 1 0 1 1 1
1 1 0 1 0 0 1
0 0 1 * 1 1 1
1 1 0 1 1 1 1
0 0 1 1 0 0 1

주난이를 뜻하는 *은 (3, 4)에 있고, 초코바를 가진 학생 #는 (1, 2)에 있다. 0은 장애물이 없는 빈 공간임을 뜻하고, 1은 친구들이 서있음을 의미한다. 다음은 주난이의 점프에 따른 생존(?) 학생들의 변화이다.

1 # 1 0 1 1 1
1 1 0 0 0 0 1
0 0 0 * 0 1 1
1 1 0 0 1 1 1
0 0 1 1 0 0 1

1 # 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 * 0 0 1
0 0 0 0 0 1 1
0 0 0 0 0 0 1

0 X 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 * 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

위의 예시에서 주난이는 3번의 점프 만에 초코바를 훔쳐간 범인을 찾아낼 수 있다!

주난이를 빨리 멈춰야 교실의 안녕을 도모할 수 있다. 주난이에게 최소 점프 횟수를 알려줘서 교실을 지키자.

 

 

입력:

첫째 줄에 주난이가 위치한 교실의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 300)

 

둘째 줄에 주난이의 위치 x1, y1과 범인의 위치 x2, y2가 주어진다. (1 ≤ x1, x2 ≤ N, 1 ≤ y1, y2 ≤ M)

 

이후 N×M 크기의 교실 정보가 주어진다. 0은 빈 공간, 1은 친구, *는 주난, #는 범인을 뜻한다.

 

 

출력:

주난이가 범인을 잡기 위해 최소 몇 번의 점프를 해야 하는지 출력한다.

 

 

 

문제 이해:

처음 문제를 보고 예제 입력 1에 대해 Step마다  어떻게 변하는지 잘 나와있지만 작성자는 잘 이해를 못하였다. 따라서 이해하는데 좀 오래걸렸다. 

 

예제 입력 1에 대해 더 쉽게 설명하면 다음과 같다.

위는 처음 상태이다 *에서 시작하여 상 하 좌 우에 전파하면 

4가지 방향 모두 친구들을 쓰러뜨렸기 때문에 이대로 step을 종료한다.

 

이 다음 Step은 다음과 같이 전파된다.

결과:

작성자는 이부분이 이해가 가지 않았었다.

결론은 시작점에서 시작하여 상 하 좌 우가 0인 부분이면 친구들을 쓰러뜨리지 않았기 때문에 친구(1)을 만날때 까지 전파하는 시스템이다.

 

 

구현 방향:

이 문제를 처음 접했을 때, 가장 먼저 BFS(너비 우선 탐색) 방식이 떠올랐다. 다만 주의해야 할 점은, 단순히 한 단계(step)마다 상·하·좌·우를 한 번만 검사하는 것이 아니라, 빈 칸(0)을 만나면 계속해서 연결된 모든 빈 칸을 탐색해야 한다는 점이다.

이를 구현하기 위해 큐를 활용하였다.

• 현재 위치에서 상·하·좌·우를 확인했을 때, 만약 값이 1이라면 해당 위치를 즉시 0으로 바꾸되 큐에는 넣지 않는다. 이렇게 처리된 1은 다음 단계에서 빈 칸처럼 활용된다.
• 반대로 값이 0이라면, 큐에 넣어 연속적으로 탐색할 수 있도록 한다.

이 과정을 큐가 빌 때까지 반복하면, 하나의 단계(step)가 끝난 것이다. 그리고 단계가 끝날 때마다 점프 횟수를 하나씩 증가시킨다.

최종적으로, 어느 단계에서든 상·하·좌·우 중에 목표 지점(#)이 존재한다면 탐색을 종료하고, 해당 단계 수가 최소 점프 횟수가 된다.

 

이를 코드로 그대로 구현하면 다음과 같다.

 

 

정답코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int x1,y1,x2,y2;
    static char[][] matrix;
    static boolean[][]visited=new boolean[301][301];


    public static int bfs(int x, int y){
        int result=0;
        boolean flag=false;
        visited[x][y]=true;

        Queue<int[]> q=new LinkedList<>();
        q.add(new int[]{x,y});

        while (true){
            result++;
            visited=new boolean[301][301]; //방문여부 초기화
            visited[x][y]=true;
            q.add(new int[]{x,y});
            while (!q.isEmpty()){
                int[] arr = q.poll();
                int curX= arr[0];
                int curY= arr[1];
                //상하좌우에 목적지가 있을 경우
                if((curX>0&&matrix[curX-1][curY]=='#')||( curY<M-1&&matrix[curX][curY+1]=='#')
                    ||(curX<N-1 &&matrix[curX+1][curY]=='#')||(curY>0 && matrix[curX][curY-1]=='#')) return result;

                //상 이며 0일 경우
                if(curX>0 && !visited[curX-1][curY] && matrix[curX-1][curY]=='0'){
                    q.add(new int[]{curX-1,curY});
                    visited[curX-1][curY]=true;
                }

                //상 이며 1일 경우
                if(curX>0 && !visited[curX-1][curY] && matrix[curX-1][curY]=='1'){
                    matrix[curX-1][curY]='0';
                    visited[curX-1][curY]=true;
                }


                //하 이며 0일 경우
                if(curX<N-1 && !visited[curX+1][curY] && matrix[curX+1][curY]=='0'){
                    q.add(new int[]{curX+1,curY});
                    visited[curX+1][curY]=true;
                }

                //하 이며 1일 경우
                if(curX<N-1 && !visited[curX+1][curY] && matrix[curX+1][curY]=='1'){
                    matrix[curX+1][curY]='0';
                    visited[curX+1][curY]=true;
                }


                //좌 이며 0일 경우
                if(curY>0 && !visited[curX][curY-1] && matrix[curX][curY-1]=='0'){
                    q.add(new int[]{curX,curY-1});
                    visited[curX][curY-1]=true;
                }
                //좌 이며 1일 경우
                if(curY>0 && !visited[curX][curY-1] && matrix[curX][curY-1]=='1'){
                    matrix[curX][curY-1]='0';
                    visited[curX][curY-1]=true;
                }

                //우 이며 0일 경우
                if(curY<M-1 && !visited[curX][curY+1] && matrix[curX][curY+1]=='0'){
                    q.add(new int[]{curX,curY+1});
                    visited[curX][curY+1]=true;

                }

                //우 이며 1일 경우
                if(curY<M-1 && !visited[curX][curY+1] && matrix[curX][curY+1]=='1'){
                    matrix[curX][curY+1]='0';
                    visited[curX][curY+1]=true;
                }
            }

        }
    }

    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());

        matrix=new char[N][M];

        StringTokenizer st1=new StringTokenizer(br.readLine());
        x1=Integer.parseInt(st1.nextToken());
        y1=Integer.parseInt(st1.nextToken());
        x2=Integer.parseInt(st1.nextToken());
        y2=Integer.parseInt(st1.nextToken());

        for (int i=0; i<N; i++){
            StringBuilder sb=new StringBuilder(br.readLine());
            for(int j=0; j<M; j++){
                matrix[i][j]=sb.charAt(j);
            }
        }

        //탐색 시작
        int result = bfs(x1-1, y1-1);

        //결과 출력
        System.out.println(result);


    }
}

 

 

 

마무리하며:

작성자는 평소 BFS/DFS 탐색을 구현할 때 직관성을 선호하여, 상·하·좌·우 탐색을 배열(dx, dy)로 처리하지 않고 각각의 방향을 별도의 if문으로 작성하는 방식을 자주 사용하였다.

 

이 방식은 처음에는 코드의 흐름을 이해하기 쉽게 만들어 준다는 장점이 있다.

 

그러나 이번 문제를 풀면서, 이러한 접근이 코드 중복을 양산하고 오히려 전체 구조의 가독성을 떨어뜨릴 수 있다는 한계를 직접 경험했다.

 

결과적으로, 경우에 따라서는 직관성을 위해 배열을 쓰지 않는 방법보다, 배열을 사용하여 반복을 단순화하는 방식이 훨씬 더 깔끔하고 유지보수에도 유리할 수 있음을 깨달았다.

 

감사합니다.