[Baekjoon] 14546_Prison Break

문제(출처: https://www.acmicpc.net/problem/14546)

---

< Prison Break >

 

문제 풀이 

 

bfs를 사용하여 문제를 해결한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class _14546_ { // Prison Break
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static char arr[][];
	static boolean visited[][];
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int P = Integer.parseInt(bf.readLine());
		for (int t = 0; t < P; t++) {
			st = new StringTokenizer(bf.readLine());
			int L = Integer.parseInt(st.nextToken());
			int W = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken())-1;
			int B = W-Integer.parseInt(st.nextToken()) ;
			int C = Integer.parseInt(st.nextToken())-1;
			int D = W-Integer.parseInt(st.nextToken()) ;
			arr = new char[W][L];
			visited = new boolean[W][L];
			for (int i = 0; i < W; i++) {
				String str = bf.readLine();
				for (int j = 0; j < L; j++) {
					arr[i][j] = str.charAt(j);
				}
			}
			bw.write(bfs(B, A, D, C) + "\n");
		}
		bw.flush();
	}
	private static String bfs(int a, int b, int c, int d) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { a, b });
		visited[a][b] = true;
		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 4; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < arr.length && y >= 0 && y < arr[0].length && arr[x][y] == arr[a][b]
						&& !visited[x][y]) {
					if (x == c && y == d) {
						return "YES";
					}
					visited[x][y] = true;
					queue.add(new int[] { x, y });
				}
			}
		}
		return "NO";
	}
}

변수)
dx, dy : 상하좌우
arr : 배열 정보
visited : 방문 여부
P : 테스트 케이스 수
L, W : 배열 크기
A, B, C, D : 시작 위치, 도착 위치

 

테스트 케이스 수를 입력받는다. 테스트 케이스 수만큼 다음 과정을 반복한다. 배열 크기와 시작, 도착 위치를 입력받고 배열 크기만큼 배열 정보를 입력받는다. bfs를 호출하여 반환 값을 출력한다.

 

bfs (시작 좌표, 도착 좌표)

큐에 시작 좌표를 저장하고 시작 위치를 true로 저장한다. queue가 빌 때까지 다음 과정을 반복한다. 

1) queue poll

2) 4방향을 탐색하며 배열 범위 안이고 시작 위치 값과 이동할 위치 값이 같고 아직 방문하지 않은 곳이라면 방문 표시 및 queue에 추가한다. 만약 이동할 위치 값이 도착 위치 값과 일치한다면 YES를 반환한다.

---

---