[SW1953] 탈주범 검거

 SW Expert Academy - 탈주범 검거 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq&categoryId=AV5PpLlKAQ4DFAUq&categoryType=CODE&problemTitle=sw&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

SW Expert Academy

 

문제 입출력

3
5 6 2 1 3
0 0 5 3 6 0
0 0 2 0 2 0
3 3 1 3 7 0
0 0 0 0 0 0
0 0 0 0 0 0
5 6 2 2 6
3 0 0 0 0 3
2 0 0 0 0 6
1 3 1 1 3 1
2 0 2 0 0 2
0 0 4 3 1 1
10 10 4 3 9
0 0 0 0 0 0 0 0 0 0
0 0 0 7 5 0 5 0 0 0
0 0 3 2 2 6 0 0 0 0
0 4 7 2 2 2 7 0 0 4
0 3 0 1 1 2 2 0 0 5
0 5 6 1 1 1 1 6 2 5
7 4 1 2 0 0 4 6 0 0
5 3 1 7 0 2 2 6 5 7
7 3 2 1 1 7 1 0 2 7
3 4 0 0 4 0 5 1 0 1

#1 5
#2 15
#3 29

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;


public class Solution {
	static int ans, dep, T, N, M, R, C, L;
	static int[][] map;
	static boolean[][] visit;

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	static int[][] dyx = {
	                {}, // dummy
	                { 0, 1, 2, 3 }, // 상하좌우
	                { 0, 1 }, // 상하
	                { 2, 3 }, // 좌우
	                { 0, 3 }, // 상우
	                { 1, 3 }, // 하우
	                { 1, 2 }, // 하좌
	                { 0, 2 }, // 상좌
	};

	static Queue<int[]> q = new ArrayDeque<>();
	static StringBuilder sb = new StringBuilder();


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			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());

			// 초기화
			q.clear();
			dep = 1;
			ans = 1;
			map = new int[N][M];
			visit = 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());
			}

			// 탐색
			bfs(R, C);

			// 출력
			sb.append("#" + t + " " + ans + "\n");
		}

		System.out.println(sb.toString());

	} // end main


	private static void bfs(int sy, int sx) {
		q.offer(new int[] { sy, sx });
		visit[sy][sx] = true;

		while (!q.isEmpty()) {
			int size = q.size();

			if (dep++ == L) return;

			for (int i = 0; i < size; i++) {
				int[] yx = q.poll();
				int y = yx[0];
				int x = yx[1];

				for (int d : dyx[map[y][x]]) {
					int ny = y + dy[d];
					int nx = x + dx[d];

					if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
					if (visit[ny][nx]) continue;
					if (map[ny][nx] == 0) continue;

					boolean flag = false;
					for (int nd : dyx[map[ny][nx]]) {
						// if (nd == (d % 2 == 0 ? d + 1 : d - 1)) flag = true;
						int nny = ny + dy[nd];
						int nnx = nx + dx[nd];

						if (y == nny && x == nnx) flag = true;
					}

					if (flag) {
						q.offer(new int[] { ny, nx });
						visit[ny][nx] = true;
						ans++;
					}

				}

			}

		}

	} // end bfs

}

• bfs 를 이용하여 풀 수 있는 문제 입니다.
• bfs 탐색을 할때마다 depth 를 잽니다. 만약 그 depth 가 L이 된다면 종료를 합니다.
• 델타를 이용해서 터널의 배열을 생성합니다.
• 방문하고자 하는 터널이 현재 터널과 맞닿아 있어야지 해당 터널로 이동할 수 있습니다.
  • 이는 y == nny && x == nnx 부분으로 구현하였습니다.
  • for문을 돌면서 방문하고자 하는 터널의 입구가 현재 터널의 출구와 맞닿아있는지 확인합니다.
• 문제를 풀면서 큰 실수를 한 게 있습니다.. 로직이 분명 맞는데 계속 안풀려서 보니 큐를 초기화를 안했더군요..
• 여러분도 이를 조심하시길 바래요..

 

 

 

 

 

 

 

 

 

# SWEA 탈주범 검거 bfs java # SW 탈주범 검거

---