728x90
문제
1 | 0 | 1 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 1 | 1 |
위와 같은 미로가 주어졌을 때 도착지까지 갈 수 있는
최단 경로를 구하는 문제
접근 방식
기존 BFS 알고리즘으로 문제를 풀 때는 방문 여부만 기록했다면
이제는 방문 여부와 출발지로부터의 거리도 기록해주면 된다.
1 | 0 | 9 | 10 | 11 | 12 |
2 | 0 | 8 | 0 | 12 | 0 |
3 | 0 | 7 | 0 | 13 | 14 |
4 | 5 | 6 | 0 | 14 | 15 |
도착지를 처음 방문 했을 때가 가장 빠른 최단 경로일테니
출발지에서 도착지까지의 거리를 출력해주면 된다.
조심해야 할건 같은 지점에서 갈 수 있는 경로의 거리는
서로 같아야 한다.
1 | 0 | 9 | 10 | 11 | 13 |
2 | 0 | 8 | 0 | 14 | 0 |
3 | 0 | 7 | 0 | 15 | 16 |
4 | 5 | 6 | 0 | 17 | 18 |
이런식으로 되면 잘못된 결과가 나오게 된다.
풀이
public class Main {
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] maze = new int[n][m];
boolean[][] isVisited = new boolean[n][m];
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split("");
for (int j = 0; j < m; j++) {
maze[i][j] = Integer.parseInt(input[j]);
}
}
Queue<Pair> queue = new ArrayDeque<>();
isVisited[0][0] = true;
queue.offer(new Pair(0, 0, 1));
while (!queue.isEmpty()) {
Pair cur = queue.poll();
if (cur.x == n - 1 && cur.y == m - 1) {
System.out.println(cur.distance);
break;
}
for (int dir = 0; dir < 4; dir++) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m)
continue;
if (maze[nx][ny] == 0 || isVisited[nx][ny])
continue;
isVisited[nx][ny] = true;
queue.offer(new Pair(nx, ny, cur.distance + 1));
}
}
}
private static class Pair {
int x;
int y;
int distance;
public Pair(int x, int y, int distance) {
this.x = x;
this.y = y;
this.distance = distance;
}
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 4179번 : 불! (0) | 2023.10.10 |
---|---|
[백준] 7576번 : 토마토 (2) | 2023.10.10 |
[BFS] 구현 및 팁 (1) | 2023.10.09 |
[백준] 1926번 : 그림 (1) | 2023.10.09 |
[백준] 2504번 : 괄호의 값 (1) | 2023.10.08 |