[SWEA] 1953. 탈주범 검거(자바 JAVA)

[ 문제 ]  [SWEA] 1953. 탈주범 검거(자바 JAVA)

 

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq 

SW Expert Academy

---

# 접근 방법 및 풀이 

 

• BFS + 구현 문제이다. 
• 처음에 그냥 터널이 깔린 곳은 다 갈 수 있는 줄 알았는데, 터널이 서로 연결될 수 있는 구조일때만 갈 수 있다.
• 1~7번 터널 중, "현재 터널 번호에 따라 살펴볼 수 있는 방향"과 "터널 번호에 따라 연결될 수 있는 구조물"이 다르다.
• 이 2가지를 처리하는게 핵심인 문제다. 물론 전부 다 고려해서 if문으로 해도 되지만 코드가 길어지는게 싫어서 다음과 같이 생각해보았다.
• 먼저 BFS 탐색시, 방향을 반시계방향으로 0(북), 1(서), 2(남), 3(동) 으로 정했다.
• 그리고 1~7번을 담을 터널 배열을 String T[] 로 표현하고, 터널이 갈 수 있는 방향으로 String값을 넣었다.
• 예를들어 ㅣ < 모양의 터널은 '북', '남'을 갈 수 있으므로 "02", ㅡ 모양의 터널은 '서', '동'을 갈 수 있으므로 "13" 으로 표현했다. 여기서 02를 쓰든 20을 쓰든 순서는 상관 없다. 13 = 31이나 같다.
• 0번은 제외하고 1~7번 터널을 배열로 표현하면 다음과 같다.
• String[] t = {"","0123", "02", "13", "03", "23", "12", "01"};
• 이제 bfs에서 4가지 방향을 탐색할 수 있는데, 이때 "현재 터널번호"가 무엇인지에 따라 갈 수 있는 방향을 if조건문을 적어주었다.
• 1번 터널을 제외한 나머지 터널들은 각각 두가지 방향밖에 탐색을 하지 못한다.
• 현재 ㅣ모양 터널이라면, 북(0), 남(2) 쪽으로 밖에 가지 못하고, ㄱ 모양 터널이면 남(2), 서(1) 밖에 가지 못한다.
• 터널에 따라 살펴볼 방향을 정해주었다면, 살펴볼 방향에 있는 터널이 "현재 터널과 연결될 수 있는지" 체크하면 된다.
• 현재 내가 d = 0, 북쪽 방향으로 간다고 생각하면 북쪽 방향에 있는 구조물은 반드시 남쪽인 2를 포함해야한다.
• 예시로, ㅣ모양의 2번 구조물에서 0 북쪽을 탐색했을때, 연결 가능한 구조물은 "2, 5, 6"번 구조물이 가능하다.
• String[] t = {"","0123", "02", "13", "03", "23", "12", "01"}; 이 터널 배열에서 2, 5, 6 구조물은 
• t[2] = "02", t[5] = "23", t[6] = "12" 로, 이렇게 2가 반드시 포함되는 걸 알 수 있다.
• 마찬가지로 2 남쪽 방향으로 살펴본다면, 남쪽의 반대인 북 0이 들어간 구조물일때만 연결이 가능하다.
• 즉, 탐색하려는 방향에 반대 방향의 숫자를 가진 터널 구조물일때만 BFS로 퍼질 수 있는 조건이다.
• 자세한건 코드참조 

# 주의할 점 

 

• 터널이 있는 곳을 다 bfs로 갈 수 있는게 아니라, 터널이 "서로 연결될 수 있는 구조"일때만 갈 수 있다.

 

JAVA 코드

package 모의SW역량테스트;

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 swea_1953_탈주범검거 {
	static int dr[] = { -1, 0, 1, 0 };
	static int dc[] = { 0, -1, 0, 1 };

	static class Point {
		int x, y, cnt;

		public Point(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	static String[] t = {"","0123", "02", "13", "03", "23", "12", "01"};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			int ans = 1;
			StringTokenizer 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 i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine());
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			} // 입력 끝

			Queue<Point> queue = new LinkedList<Point>();
			boolean visit[][] = new boolean[N][M];
			queue.add(new Point(R, C, 1));
			visit[R][C] = true;
			while (!queue.isEmpty()) {
				Point p = queue.poll();
				if (p.cnt == L)
					break;	
				int curTunnel = map[p.x][p.y];
				for (int d = 0; d < 4; d++) {
					int nr = p.x + dr[d];
					int nc = p.y + dc[d];
					if (nr < 0 || nc < 0 || nr >= N || nc >= M || visit[nr][nc] || map[nr][nc] == 0)
						continue;
					int nextTunnel = map[nr][nc];
					String opDir = Integer.toString((d + 2) % 4);
					if(!t[nextTunnel].contains(opDir))
						continue;
					if(curTunnel == 2 && d%2 != 0)
						continue;
					if(curTunnel == 3 && d%2 == 0)
						continue;
					if(curTunnel == 4 && d%3 != 0)
						continue;
					if(curTunnel == 5 && d < 2)
						continue;
					if(curTunnel == 6 && d%3 == 0)
						continue;
					if(curTunnel == 7 && d > 1)
						continue;		
					visit[nr][nc] = true;
					queue.add(new Point(nr, nc, p.cnt + 1));
					ans++;
				}
			}
			System.out.println("#" + tc + " " + ans);
		}
	}
}

 

 

 

REVIEW