[Gold IV] 주난의 난(難) - 14497 (JAVA)

문제 요약

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

‘쿵... 쿵...’

주난이는 점프의 파동으로 주변의 모든 친구들을 쓰러뜨리고(?) 누군가 훔쳐간 초코바를 찾으려고 한다. 주난이는 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번의 점프 만에 초코바를 훔쳐간 범인을 찾아낼 수 있다!

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

---

문제 분석

BFS로 탐색을 한다. 다만 탐색하는 도중 친구가 없는 0을 만나면 그 위치에서 다시 탐색을 해줘야 한다.

큐를 두 개를 사용해서 구현할까 하다가 덱을 사용하여 구현하면 될 것 같아 덱으로 구현해 봤다.

만약 BFS도중 다음 위치가 0이라면 덱의 가장 앞에, 아니라면 덱의 가장 뒤에 넣어주는 방식으로 구현했다.

---

코드

package Week16;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class BOJ_14497 {
    static int N, M;
    static int[] junan;
    static int[] target;
    static char[][] map;
    static int[] deltas = {0,-1,0,1,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());
        junan = new int[2];
        target = new int[2];
        map = new char[N][M];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++){
            if(i < 2){
                junan[i] = Integer.parseInt(st.nextToken()) -1;
            }
            else{
                target[i-2] = Integer.parseInt(st.nextToken()) -1;
            }
        }
        for(int i = 0; i < N; i++){
            map[i] = br.readLine().toCharArray();
        }
        // bfs로 탐색
        int[][] visited = new int[N][M];
        // 친구가 없는 곳에서는 다음 파동으로 넘기기 위해 deque의 앞에 다음 위치를 넣어준다.
        Deque<int[]> dq = new ArrayDeque<>();
        dq.addLast(junan);
        visited[junan[0]][junan[1]] = 1;
        // 탐색시 현재위치
        int[] curr;
        int r, c, nr, nc, result = 0;
        while(!dq.isEmpty()){
            curr = dq.pollFirst();
            r = curr[0];
            c = curr[1];
            if(Arrays.equals(curr, target)){
                // 찾음
                result = Math.max(visited[r][c]-1, result);
                break;
            }
            for(int d = 0; d < 4; d++){
                nr = r + deltas[d];
                nc = c + deltas[d+1];
                // 다음 위치가 범위를 초과했거나, 이미 탐색한 곳이면 넘어가기
                if(isArrOut(nr, nc) || visited[nr][nc] > 0)
                    continue;
                // 만약 다음 위치가 친구가 없는곳이면, 덱의 앞에 넣어서 재탐색해준다.
                if(map[nr][nc] == '0'){
                    visited[nr][nc] = visited[r][c];
                    dq.addFirst(new int[]{nr, nc});
                }
                // 다음 위치가 친구가 있는곳이니, 덱의 맨 뒤에 넣어 추후 탐색해준다.
                else{
                    visited[nr][nc] = visited[r][c] + 1;
                    dq.addLast(new int[]{nr, nc});
                }
            }
        }
        System.out.println(result);
    }
    static boolean isArrOut(int r, int c){
        return r < 0 || c < 0 || r >= N || c >= M;
    }
}

---

정리

새로 배운 내용

뭔지도 모르고 풀었는데 알고 보니 '0-1 너비 우선 탐색'이라는 이미 존재하는 알고리즘이었다.

그냥 생각해서 푼 게 존재했던 알고리즘 로직이라니.. 기분 좋다...ㅎ

개선할 점

없음

더 찾아볼만한 사항

없음

---