풀이
최단경로에 관한 문제는 DFS보다 BFS가 더 풀기 편하다.
만약 BFS와 DFS가 헷갈리고 구현하기 힘들다면 아래 유튜브를 참고하자
왜 큐가 사용되고 왜 스택이나 재귀가 사용되는지 이해되면 그 다음부턴 구현이다.
BFS
•
동서남북으로 이동할 수 있도록 좌표를 생성해준다.
•
맵의 방문 여부를 확인하기 위한 이차원 배열을 만들어준다.
•
BFS를 돌린다. BFS는 Queue를 사용해서 구현한다.
•
Node 객체는 맵의 x좌표, y좌표, 이동거리를 가지고 있다.
1.
노드를 큐에 넣고 방문처리를 해준다.
visited[x][y] = true;
Java
복사
2.
큐에 인자가 없을 때까지 반복한다.
while(!q.isEmpty())
Java
복사
3.
동서남북 모두 탐색한다.
for(int i = 0; i < 4; i++) {
int nx = node.x + dx[i];
int ny = node.y + dy[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
if(maps[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.offer(new Node(nx, ny, node.cost + 1));
}
}
}
Java
복사
4.
큐에 맵을 벗어나거나 이미 방문한 곳인지 확인하고
if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
// True
// False
}
Java
복사
True: 큐에서 Poll 되었으니 무시
False: 그 좌표를 기준으로 다시 큐에 넣어준다. (방문처리 후 노드의 cost를 1 추가 시킨다.)
visited[nx][ny] = true;
q.offer(new Node(nx, ny, node.cost + 1));
Java
복사
5.
큐가 비었다면 더 이상 탐색할 수 없다는 것이다.
6.
큐에 인자가 없어지기 전에 목표 지점에 도착했다면 cost를 반환한다.
if(node.x == n - 1 && node.y == m - 1) return node.cost;
Java
복사
전체 코드
import java.util.*;
class Solution {
// 1
int[] dx = {0, 1, 0, -1};
int[] dy = {-1, 0, 1, 0};
// 2
boolean[][] visited;
int n, m;
public int solution(int[][] maps) {
n = maps.length;
m = maps[0].length;
visited = new boolean[n][m];
return bfs(0, 0, maps);
}
public int bfs(int x, int y, int[][] maps) {
Queue<Node> q = new LinkedList<>();
q.offer(new Node(x, y, 1));
visited[x][y] = true;
while(!q.isEmpty()) {
Node node = q.poll();
if(node.x == n - 1 && node.y == m - 1) return node.cost;
for(int i = 0; i < 4; i++) {
int nx = node.x + dx[i];
int ny = node.y + dy[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
if(maps[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.offer(new Node(nx, ny, node.cost + 1));
}
}
}
}
return -1;
}
public class Node {
int x;
int y;
int cost;
public Node(int x, int y, int cost) {
this.x = x;
this.y = y;
this.cost = cost;
}
}
}
Java
복사