[SWEA 1953] [모의 SW 역량테스트] 탈주범 검거

문제

• SWEA 1953
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

DFS(예정)

BFS

나는 아직 BFS가 익숙하기 때문에 큐를 사용해서 문제를 해결했다.

1. 터널좌표의 정보를 담아줄 클래스 Point를 좌표 r,c, 갈 수 있는 터널방향을 표시할 dir배열로 구성한다.
2. 탈주범이 탈출한시간 뒤 터널에 도달하는데 1시간이 걸리므로 시작 시간 time은 1로 정한다.
3. 큐에 처음 맨홀 좌표 R,C를 넣고 방문처리를 한다.
   1-1. 큐에서 꺼내서 이 터널에서 갈 수 있는 방향을 셋팅한다 => setDir()
   1-2. 상,좌,하,우를 돌면서 다음 좌표로 갈 수 있는지 확인한다.
   => 범위 안에 드는지, 아직 방문하지 않았는지, 터널인지
   1-3. 갈 수 있다면 터널이 서로 연결되어 있는지 확인하기 위해 다음 좌표의 방향을 셋팅한다 => setDir()
   1-4. 현재 방향이 상이면 다음 방향은 하, 좌이면 다음 방향은 우로 연결되어 있어야 갈 수 있다. 방향 배열 dr,dc의 인덱스 0,1,2,3에서 상-하와 좌-우의 차는 2이고 역도 성립한다.

     	if(p.dir[d] && np.dir[(d+2)%4]) { //현재 바라보는 방향으로 연결되어 있으면
                            queue.add(new Point(nr, nc));
                            visited[nr][nc] = true; //이 장소에 올수 있다고 표시
                            count++;
                        }
   

   따라서 위와 같이 현재 좌표에서 방향 d가 true이고, 다음 좌표에서 방향 (d+2)%4가 true이면 연결되어 있으므로 큐에 넣고 방문 가능 표시를 해준다.
   (d+2)%4를 한 이유는 만약 d가 우로 3일 경우 d+2는 5가 되므로 이를 4로 나눈 나머지인 1이 좌가 될 수 있기 때문이다. 즉, d+2가 3보다 클 경우를 처리해주기 위해 나머지 처리를 해주었다.
   그리고 탈주범이 위치할 수 있는 장소의 개수를 하나 증가시키기 위해 count를 하나 증가시킨다.

새로 알게된 사실은 DFS로 접근하게 되면 bfs처럼 count를 실시간으로 증가시키면 안되고, 나중에 또 그 좌표에 방문할 수 있기 때문에 모든 탐색이 끝난 마지막에 2중 for문을 돌면서 그래프에 방문가능표시 부분을 세어줘야한다는 점이다.
이번주 주말에 DFS로 다시 풀어보면서 그 차이를 이해해보도록 하자.

코드

1. DFS
예정

2. BFS

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

//큐에 넣을때 count를 셈
public class SWEA1953_탈주범검거 {

	static int N, M, R, C, L; // 세로, 가로, 맨홀위치, 탈출후시간
	static int[][] map;
	static boolean[][] visited;
	static int[] dr = {-1, 0, 1, 0}; //상 좌,하,우
	static int[] dc = {0, -1, 0, 1};
	static int count;

	static public class Point {
		int r;
		int c;
		boolean[] dir = new boolean[4]; //이 좌표에서 갈 수 있는 방향 true

		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());

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

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

			count = 1; //탈주범이 위치할 수 있는 장소 개수
			go();

			System.out.println("#" + tc + " " + count);
		}
	}

	private static void go() {
		int time = 1; // 시작 시간
		Queue<Point> queue = new LinkedList<>();
		queue.add(new Point(R, C));
		visited[R][C] = true;

		while (!queue.isEmpty()) {
			if (time >= L) return;
			int size = queue.size();
			for(int s=0; s<size; s++) {
				Point p = queue.poll();
				setDir(p); //이 터널에서 갈 수 있는 방향을 셋팅

				for (int d = 0; d < 4; d++) {
					int nr = p.r + dr[d];
					int nc = p.c + dc[d];
					
					if (nr >= 0 && nr < N && nc >= 0 && nc < M && !visited[nr][nc] && map[nr][nc] > 0) {
						//터널이 연결되어 있는지 판단
						Point np = new Point(nr, nc);
						setDir(np); //다음 터널에 연결된 방향을 구하고
						if(p.dir[d] && np.dir[(d+2)%4]) { //현재 바라보는 방향으로 연결되어 있으면
							queue.add(new Point(nr, nc));
							visited[nr][nc] = true; //이 장소에 올수 있다고 표시
							count++;
						}
					}
				}
			}
			time++;
		}
	}

	private static void setDir(Point p) { //이 좌표에서 갈수있는 방향 셋팅
		if(map[p.r][p.c] == 1) { //상,좌,하,우
			p.dir[0] = true; p.dir[1] = true; p.dir[2] = true; p.dir[3] = true;
			
		}else if(map[p.r][p.c] == 2) { //상, 하
			p.dir[0] = true; p.dir[2] = true;

		}else if(map[p.r][p.c] == 3) { //좌, 우
			p.dir[1] = true; p.dir[3] = true;

		}else if(map[p.r][p.c] == 4) { //상, 우
			p.dir[0] = true; p.dir[3] = true;

		}else if(map[p.r][p.c] == 5) { //하, 우
			p.dir[2] = true; p.dir[3] = true;

		}else if(map[p.r][p.c] == 6) { //하, 좌
			p.dir[1] = true; p.dir[2] = true;

		}else if(map[p.r][p.c] == 7) { //상,좌
			p.dir[0] = true; p.dir[1] = true;
		}
	}
}