[프로그래머스] [Level 2] [DFS/BFS] 게임 맵 최단거리

게임 맵 최단거리

프로그래머스

 

• 내 풀이 : ⚠️ fail 
  • 각각의 거리를
  • 더이상 갈 곳이 없는 것을 표현하기가 어려웠음
  • 여러방향으로 한 곳에 도착했을 때 가장 작은 값을 선택하도록 코드를 짰는데 이미 방문한 곳에는 다시 방문할 필요가 없었음

from collections import deque
from collections import defaultdict

def bfs(maps,dx,dy):
    n,m=len(maps),len(maps[0]) 
    #남,동,북,서 (가장 오른쪽 아래로 가야하므로)
    xdir=[1,0,-1,0]
    ydir=[0,1,0,-1]
    
    visited=defaultdict(list)
    for i in range(n):
        for j in range(m):
            visited[i].append(0)
    visited[0][0]=1
    
    queue=deque()
    queue.append((dx,dy))
    
    while queue:
        count=0
        dx,dy=queue.popleft()
        if dx==n-1 and dy==m-1:
            return maps[dx][dy]
    
        for i in range(4):
            nx,ny=dx,dy
            nx+=xdir[i]
            ny+=ydir[i]
            
            if nx==0 and ny==0:
                count+=1
                continue
            if nx<0 or nx>=n or ny<0 or ny>=m or maps[nx][ny]==0:
                count+=1
                if count==4:
                    return -1  
                continue
                   
            if maps[nx][ny]==1: #처음 도착한 경우
                maps[nx][ny]=maps[dx][dy]+1
                
            else:
                #그전의 위치 수+1, 현재 값 중 작은 값으로 업데이트
                if maps[nx][ny]<maps[dx][dy]+1:
                    count+=1
                    if count==4:
                        return -1
                else:
                    maps[nx][ny]=min(maps[nx][ny],maps[dx][dy]+1) 
                    
            visited[nx][ny]=1
            queue.append((nx,ny))

def solution(maps):
    result=bfs(maps,0,0)  

    return result

 

• 다른 사람 풀이
  • maps를 건들이지 X 
    
    • (x,y) : 거리 → 딕셔너리 이용해서 거리 계산
  • 0<=nx<n 같은 부등호 계산 한 번에 가능
  • 다음 위치에서 for문 돌면서 접한 4면을 모두 진행
  • 이미 방문한 곳은 다시 계산 하지 X
  • ⚠️2차원 리스트 [[0]*m]*n 하면 한줄 값 바꾸면 아랫줄들도 함께 바뀜
    • → [[False for _ in range(m)] for _ in range(n)]
  • 값 2개를 한번에 동일한지 비교 →묶어서 비교 (nx,ny)==(n-1,m-1)
  • queue= deque()안에 값을 바로 넣을 경우 리스트 안에 set을 넣기 queue=deque([(x,y)] )
    • queue=deque() 후 queue.append((x,y)) 하는 경우는 set만 바로 넣어도 가능

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    visited = [[False for _ in range(m)] for _ in range(n)]
    return bfs(maps, 0, 0, visited)
    
def bfs(maps, x, y, visited):
    n, m = len(maps), len(maps[0])
    queue = deque([(x, y)])
    visited[x][y] = True
    distance = {(x, y): 0}
    #북, 남, 서 ,동
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and maps[nx][ny]:
                if (nx, ny) == (n-1, m-1): return distance[(x, y)] + 2
                queue.append((nx, ny))
                distance[(nx, ny)] = distance[(x, y)] + 1
                visited[nx][ny] = True
    return -1