[SWEA] 1953 탈주범 검거 - JAVA

1. 문제

SW Expert Academy

---

2. 풀이

입력

테스트케이스와 무관하게 항상 필요한 변수들이다. 메인에 저장했다.

int[][] deltas	상하좌우 다음 이동 위치
int[][] pipe	파이프 타입 별 움직일 수 있는 deltas 인덱스
int[][] connect	방향 별 이을 수 있는 pipe 인덱스
Queue<int[]> queue	bfs에 사용할 queue

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;

StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(in.readLine());

int[][] deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//상-하-좌-우
int[][] pipe = {{0, 1, 2, 3}, {0, 1}, {2, 3}, {0, 3}, {1, 3}, {1, 2}, {0, 2}};//파이프 방향
int[][] connect = {{1, 2, 5, 6}, {1, 2, 4, 7}, {1, 3, 4, 5}, {1, 3, 6, 7}};//방향별 가능한 파이프
Queue<int[]> queue = new ArrayDeque<>();

 

테스트케이스마다 입력한 변수들이다. 

N,M	세로, 가로
R,C	맨홀 세로, 맨홀 가로
L	탈출 후 소요된 시간
int[][] map	입력정보

st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());//세로
int M = Integer.parseInt(st.nextToken());//가로
int R = Integer.parseInt(st.nextToken());//맨홀 세로위치
int C = Integer.parseInt(st.nextToken());//맨홀 가로위치
int L = Integer.parseInt(st.nextToken());//탈출 후 소요된 시간

int[][] map = new int[N][M];

for (int n = 0; n < N; n++) {
   st = new StringTokenizer(in.readLine());
   for (int m = 0; m < M; m++) {
      map[n][m] = Integer.parseInt(st.nextToken());
   }
}

 

탐색

BFS로 진행했다. 이미 방문한 곳은 map을 -1로 변경했다.

1.  처음 맨홀 위치에 있을 때 이미 한 시간이 지난 뒤다. 따라서 queue에 시간을 넣을 때 1을 넣는다. result도 1로 시작한다.

2.  시간이 이미 L인 곳은 뽑기만 하고 더 이상 다음 값을 탐색하지 않는다.

3.  파이프의 타입에 따라 가능한 방향만 탐색한다.

4.  탐색 방향으로 다음 위치를 찾는다.

        1) 그 위치가 범위에 벗어나지 않고

        2) 파이프가 있는 위치라면

        3) 그 파이프가 현재의 탐색 방향에서 이을 수 있는 파이프인지 확인한다.

        4) connect를 오름차순으로 넣었기 때문에 다음위치의 파이프숫자가 connect보다 큰데 못찾은 상태면 끝낸다. 

5.  1) ~ 4)에 해당하지 않는 위치면 map[nr][nc]를 -1로 변경하고 경우의 수 result를 하나 더한다.

6.  마지막에 형식에 맞춰서 result를 출력한다.

int result = 1;
queue.offer(new int[]{R, C, map[R][C], 1});
map[R][C] = -1;//방문처리
while (!queue.isEmpty()) {
   int[] pos = queue.poll();
   int time = pos[3];
   if (time == L) continue;

   R = pos[0];
   C = pos[1];
   int type = pos[2];

   for (int d : pipe[type - 1]) {
      int nr = R + deltas[d][0];
      int nc = C + deltas[d][1];
      int ntype;
      if (nr >= 0 && nr < N && nc >= 0 && nc < M && (ntype = map[nr][nc]) > 0) {
         for (int x : connect[d]) {
            if(x>ntype) break;
            if(x!=ntype) continue;

            queue.offer(new int[]{nr, nc, ntype, time + 1});
            map[nr][nc] = -1;
            result++;
         }
      }
   }
}

sb.append('#').append(tc).append(' ').append(result).append('\n');

---

3. 결과