SWEA_1953_탈주범검거_JAVA
문제 : 탈주범 검거
SWEA문제는 로그인을 해야 열람할 수 있습니다.
링크 : SWEA_1953_탈주범검거
접근 방식
파이프는 뚫려있는 방향에 따른 종류가 나뉘어있고, 탈주한 범인이 들어간 위치로부터, 일정 시간이 지난 후에 탈주범이 있을 법한 위치를 찾아야 하는 문제이다.
파이프의 상태는 배열에 숫자로 주어지며, 탈주범이 처음 도망간 위치로부터 BFS를 이용하여 범위를 구하면 되는 문제인데, 이제 여기서 어려운 점이 파이프가 연결되어 있는 경우에만 이동할 수 있다는 것이다.
따라서 파이프의 상태에 따라서 연결 가능한지 연결이 불가능 한지 체크하는 로직을 짜는 부분이 중요하다고 할 수 있다.
BFS를 진행하면서 현재 파이프와 이동하고자 하는 위치의 파이프의 종류를 비교한다. 그 결과 연결이 되어있는 상태일 경우에만 이동하도록 하면 된다.
이렇게 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;
public class SW_1953_탈주범검거 {
static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
/*
* 1. 상하좌우 : 0,1,2,3 2. 상하 : 1,3 3. 좌우 : 0,2 4. 상우 : 0,3 5. 하우 : 0,1 6. 하좌 : 1,3
* 7. 상좌 : 2,3
*/
static int N, M, R, C, L, arr[][];
static int cnt;
/*
* 1 = 어디에나 연결 가능 2 =
*/
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++) {
StringTokenizer st = new StringTokenizer(in.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());
arr = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine(), " ");
for (int j = 0; j < M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
cnt = 0;
bfs(R, C, new boolean[N][M]);
System.out.printf("#%d %d\n",tc,cnt);
}
}
public static void bfs(int x, int y, boolean[][] visited) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] { x, y, 1 });
visited[x][y] = true;
cnt++;
while (!queue.isEmpty()) {
int[] node = queue.poll();
if (node[2] >= L) {
break;
}
// System.out.println("node2:"+node[2]+" x : "+ node[0]+" y : "+node[1]);
int pipe = arr[node[0]][node[1]];
for (int d = 0; d < 4; d++) {
int dx = node[0] + dir[d][0];
int dy = node[1] + dir[d][1];
if (dx >= 0 && dx < N && dy >= 0 && dy < M) {
if (arr[dx][dy] != 0 && !visited[dx][dy]) {
int np = arr[dx][dy];
if (d == 0) {
if (pipe == 1 || pipe == 2 || pipe == 4 || pipe == 7) {
if (np == 1 || np == 2 || np == 5 || np == 6) {
visited[dx][dy] = true;
queue.offer(new int[] { dx, dy, node[2] + 1 });
cnt++;
}
}
} else if (d == 1) {
if (pipe == 1 || pipe == 2 || pipe == 5 || pipe == 6) {
if (np == 1 || np == 2 || np == 4 || np == 7) {
visited[dx][dy] = true;
queue.offer(new int[] { dx, dy, node[2] + 1 });
cnt++;
}
}
} else if (d == 2) {
if (pipe == 1 || pipe == 3 || pipe == 6 || pipe == 7) {
if (np == 1 || np == 3 || np == 4 || np == 5) {
visited[dx][dy] = true;
queue.offer(new int[] { dx, dy, node[2] + 1 });
cnt++;
}
}
} else if (d == 3) {
if (pipe == 1 || pipe == 3 || pipe == 4 || pipe == 5) {
if (np == 1 || np == 3 || np == 6 || np == 7) {
visited[dx][dy] = true;
queue.offer(new int[] { dx, dy, node[2] + 1 });
cnt++;
}
}
}
}
}
}
}
}
}