[BOJ] 14497 주난의 난 - JAVA

1. 문제

14497번: 주난의 난(難)

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

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

 

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

 

0이면 점프 파동이 이어지고, 1이면 파동이 끝나고 새 파동이 시작되어야 한다.

---

2. 풀이

int N,M	교실크기
int x1,y1,x2,y2	주난이 위치, 도둑 위치
char[][] input	처음 교실 상태
int[][] count	파동이 도달할 때까지의 점프 횟수
int[][] delta	이동

 

범위체크

delta 배열로 만들어진 ni,nj가 범위에 벗어나거나 이미 방문한 적 있는지 확인한다.

public static boolean isValid(int i, int j) {
   return i >= 0 && i < N && j >= 0 && j < M && count[i][j]==-1;
}

 

BFS

우선순위 큐를 써도 되지만 그렇게 하지 않은 이유는 값이 0과 1밖에 없기 때문이다. Deque을 사용해서 앞뒤로 offer한다. 0이면 앞, 1이면 뒤로 더해야한다. 최소 점프 횟수를 구해야 하기 때문이다.

 

1.  주난이 첫 위치에 0을 저장한다.

2.  덱이 빌 때까지 탐색한다.

2-1.  next i, next j의 범위를 isValid 메서드로 체크한다.

2-2.  만약 그 자리가 비어있다면 다시 뛰지 않아도 된다. 현재의 점프 수와 동일한 값을 저장한다. 값이 변하지 않았기 때문에 deque의 맨 앞에 더한다. (그래야 자연스럽게 정렬이 됨)

2-3.  만약 그 자리에 사람이 있다면 현재의 점프 수 + 1을 저장한다. deque의 맨 뒤에 더해서 정렬이 되도록 한다.

3.  범인 자리의 count 값을 반환한다.

public static int find() {
   Deque<int[]> deque = new ArrayDeque<>();
   deque.offer(new int[]{x1, y1});
   count[x1][y1] = 0;

   int[] node;
   int ni, nj;
   while (!deque.isEmpty()) {
      node = deque.poll();

      for (int d = 0; d < 4; d++) {
         ni = node[0] + delta[d][0];
         nj = node[1] + delta[d][1];
         if (!isValid(ni, nj)) continue;

         if(input[ni][nj]=='0') {
            count[ni][nj] = count[node[0]][node[1]];
            deque.offerFirst(new int[]{ni,nj});
         }
         else {
            count[ni][nj] = count[node[0]][node[1]] + 1;
            deque.offerLast(new int[]{ni,nj});
         }
      }
   }

   return count[x2][y2];
}

---

3. 결과

ㅋㅋㅋㅋㅋㅋㅋㅋ BFS가지고 이렇게 많이 틀리다니 ....