[백준/Python] 16928번_뱀과 사다리 게임(BFS)

📌문제 유형

그래프 이론, 그래프 탐색, BFS

 

📌문제

16928번: 뱀과 사다리 게임

 

 

📌나의 문제풀이

- 오답 (28% 메모리 초과)

- 메모리초과 이유

• visited[new] == 0이 아닌 경우도 고려함
  -> (그럴필요 없음) 0일 경우가 제일 최소값이기 때문
•  예) 1-3 (1번) / 1-2-3 (2번)

from collections import deque

## 입력 ##
n, m = map(int,input().split())

ladder_or_snake = {}

for _ in range(n):
    x,y = map(int,input().split())
    ladder_or_snake[x] = y

for _ in range(m):
    u,v = map(int,input().split())
    ladder_or_snake[u] = v

## 코드 작성
visited = [0 for _ in range(101)]
num = 1
q = deque([])
q.append(num)

while q:
    now = q.popleft()

    if now == 100:
        break

    for i in range(1,7):
        new = now + i
        if new < 101:
            if new in ladder_or_snake.keys():
                new = ladder_or_snake[new]

                if visited[new] == 0:
                    visited[new] = visited[now] + 1
                else:
                    visited[new] = min(visited[new], visited[now] + 1)
            else:
                
                if visited[new] == 0:
                    visited[new] = visited[now] + 1
                else:
                    visited[new] = min(visited[new], visited[now] + 1)
            
            q.append(new)
    
print(visited[100])

 

 

-정답

• 최대 100개 위치 다 순회하면서 최솟값 찾기
• start, end가 연결되는 형태 -> dict 사용

from collections import deque

## 입력 ##
n, m = map(int,input().split())

ladder_or_snake = {}

for _ in range(n):
    x,y = map(int,input().split())
    ladder_or_snake[x] = y

for _ in range(m):
    u,v = map(int,input().split())
    ladder_or_snake[u] = v

## 코드 작성
visited = [0 for _ in range(101)]
num = 1
q = deque([])
q.append(num)

while q:
    now = q.popleft()

    if now == 100:
        break

    for i in range(1,7):
        new = now + i
        if new < 101 and visited[new] == 0:
            if new in ladder_or_snake.keys():
                new = ladder_or_snake[new]

            if visited[new] == 0:
                visited[new] = visited[now] + 1
                q.append(new)
    
print(visited[100])

 

📌리뷰

- BFS는 꼭 2차원 배열을 사용하지 않아도 됨. 고정관념 탈피하기.

- 꼬리 물면서 값 변한다 - dict 사용 고려