https://www.acmicpc.net/problem/14940
정답률 37.136%
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
최소 이동거리를 거리를 구하는 문제이므로 BFS를 사용한다. 목적지에 대한 최소 이동거리를 구해야하므로 우선 목적지의 좌표부터 탐색한 뒤 BFS를 진행한다. 갈 수 있는 곳이나 0으로 둘러싸여 탐색을 못하면 원소를 -1으로 할당한다.
//백준
public class Main {
private static final int[] dr = {-1, 0, 1, 0};
private static final int[] dc = {0, 1, 0, -1};
private static int[][] map;
private static boolean[][] visit;
private static int M;
private static int N;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //세로
M = Integer.parseInt(st.nextToken()); //가로
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());
}
}
//목적지 좌표
int[] destination = new int[2];
//목적지 탐색
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 2) {
destination[0] = i;
destination[1] = j;
}
}
}
bfs(destination[0], destination[1]);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
//도달하지 않은 곳 -1
if (!visit[i][j] && map[i][j] == 1) {
map[i][j] = -1;
}
sb.append(map[i][j]).append(" ");
}
if (i != N - 1) {
sb.append("\n");
}
}
System.out.println(sb);
}
private static void bfs(int r, int c) {
map[r][c] = 0;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{r, c});
while (!queue.isEmpty()) {
int[] curPos = queue.poll();
int curR = curPos[0];
int curC = curPos[1];
for (int i = 0; i < 4; i++) {
int nextR = curR + dr[i];
int nextC = curC + dc[i];
if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= M) {
continue;
}
if (map[nextR][nextC] == 1 && !visit[nextR][nextC]) {
visit[nextR][nextC] = true;
queue.add(new int[]{nextR, nextC});
map[nextR][nextC] = map[curR][curC] + 1;
}
}
}
}
}
흔한 최소 이동 거리를 구하는 BFS 문제였다. 하지만 2차원 배열 출력도 잘해줘야 하고, 도달할 수 있지만 가지 않은 곳은 -1으로 처리해줘야 하는 등 문제에 잔실수를 유발하는 요소가 많았다. 이제 이정도 수준의 BFS는 쉽다.