[프로그래머스] PCCP 모의고사 2회 4번 보물 지도

사용 언어 - Python3

문제 - 보물 지도

https://school.programmers.co.kr/learn/courses/15009/lessons/121690

프로그래머스

 

 

정답

큐, BFS

이동하면서 신발 사용안했다면 신발사용한 nx,ny로 이동

 

1. from collections import deque

2. dx,dy 방향 상하좌우 이동

3. graph(n*m) 설정, hole 구멍위치는 1이고 나머지는 0

4. visited(n*m*2) 설정, 신발사용여부 O/X 포함한 방문여부 설정

5. 시작

queue = deque()

visited[0][0][False] = True

queue.append((0,0,False))

L = 0

 

6. 큐 한칸씩 이동

x,y,used을 queue에서 popleft로 뽑아주면서 상하좌우로 이동시킨다 x,y -> nx,ny

(이동 조건 : n*m 안에 있어야하고, 방문하지 않았어야하고, hole이면 안된다.)

nx,ny가 n-1,m-1 위치에 도달하면 바로 return L+1 / 아니라면 방문여부, queue에 append

 

만약 신발을 아직 사용하지 않았다면, nx,ny를 한번더 상하좌우로 이동한다.

 

한칸씩 이동할 때마다 L += 1 업데이트

(n-1,m-1)에 도달하지 못했다면 return -1

 

from collections import deque
def solution(n, m, hole):
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    graph = [[0] * m for _ in range(n)]
    for a,b in hole:
        graph[a-1][b-1] = 1
    
    queue = deque() 
    visited = [[[False] * 2 for _ in range(m)] for _ in range(n)] # x,y,신발사용여부
    visited[0][0][False] = True 
    queue.append((0,0,False))
    L = 0
    
    while queue:
        
        for _ in range(len(queue)):
            x,y,used = 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][used] and graph[nx][ny] == 0:
                    if (nx,ny) == (n-1,m-1):
                        return L + 1
                    visited[nx][ny][used] = True
                    queue.append((nx,ny,used))
                    
                if not used: # 신발사용하면서 이동하기
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny][used] and graph[nx][ny] == 0:
                        if (nx,ny) == (n-1,m-1):
                            return L + 1
                        visited[nx][ny][True] = True
                        queue.append((nx,ny,True))
        L += 1    
    return -1

 

 

 

레퍼런스

https://dingdingcrong.tistory.com/188

[프로그래머스] [PCCP 모의고사 #2] 보물 지도