[프로그래머스 Lv.2] 게임 맵 최단거리(DFS/BFS)
from collections import deque
def solution(maps):
answer = 0
n = len(maps) # 행
m = len(maps[0]) # 열
# 상하좌우 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
# 상하좌우 모두 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# N X M 범위를 넘는 경우
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 벽인 경우
if maps[nx][ny] == 0:
continue
# 처음 지나간 길인 경우(지나간 적이 있다면 1보다 커야 함)
if maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1 # 최단 거리 저장
queue.append((nx, ny))
if maps[n - 1][m - 1] == 1: # 도착하지 못한 경우
return -1
return maps[n - 1][m - 1] # 도착지 최단 거리
return bfs(0, 0)
import java.util.*;
class Pair {
int x;
int y;
Pair(int x, int y){
this.x = x;
this.y = y;
}
}
class Solution {
public int bfs(int x, int y, int[][] maps){
int n = maps.length;
int m = maps[0].length;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Queue<Pair> q = new LinkedList<Pair>();
q.offer(new Pair(x, y));
while(!q.isEmpty()){
Pair p = q.poll();
for(int i = 0; i < 4; i++){
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m){
continue;
}
if(maps[nx][ny] == 0){
continue;
}
if(maps[nx][ny] == 1){
maps[nx][ny] = maps[p.x][p.y] + 1;
q.offer(new Pair(nx, ny));
}
}
}
if(maps[n - 1][m - 1] == 1){
return -1;
}
return maps[n - 1][m - 1];
}
public int solution(int[][] maps) {
return bfs(0, 0, maps);
}
}