내 풀이
import sys
from collections import deque
input = sys.stdin.readline
def solution():
N,M = map(int,input().split())
graph=[i for i in range(101)]
visited = [0] * 101
for i in range(N+M):
a,b = map(int,input().split())
graph[a]=b
def bfs():
queue = deque([1])
visited[1] = 1
while queue:
x = queue.popleft()
print(x)
for i in range(1,7):
dice = x + i
if dice > 100:
continue
cnt = graph[dice]
if visited[cnt]==0:
queue.append(cnt)
visited[cnt] = visited[x] + 1
if cnt == 100:
return
bfs()
print(visited[100]-1)
solution()BFS로 풀어봤다.
포인트는, graph에다가 이동하는 숫자만큼 배분하는것이다.
가령 4에 78로 움직이는 사다리가 있다고 가정하면
graph[4] = 78로 대체하는것이다. 그 외에는 해당 숫자에 맞는 크기를 배분해준다.
배분된 숫자에 주사위 크기만큼 (1~6) 더해주고 그 크기가 100을 넘어간다면 continue를 통해 무시해준다.
주사위 자체가 1~6까지 for 문으로 돌아가기 때문에
x+1~x+6,까지는 visited[x]의 값이 같을 수 밖에 없다.
최초에 visited[1]= 1 로 시작하기 때문에 마지막에 -1을 해준다.
참고로 print(x) 주석처리 해줘야 오류 안뜬다.
다른사람의 풀이
from collections import deque
def bfs():
queue = deque([1])
visited[1] = True
while queue:
now = queue.popleft()
for move in range(1,7):
check_move = now+move
if 0 < check_move <= 100 and not visited[check_move]:
if check_move in ladder.keys():
check_move = ladder[check_move]
if check_move in snack.keys():
check_move = snack[check_move]
if not visited[check_move]:
queue.append(check_move)
visited[check_move] = True
board_cnt[check_move] = board_cnt[now] + 1
if __name__ == '__main__':
N, M = map(int,input().split())
board_cnt = [0] * 101
visited = [False] * 101
snack = dict()
ladder = dict()
for _ in range(N):
i,j = map(int,input().split())
ladder[i] = j
for _ in range(M):
i,j = map(int,input().split())
snack[i] = j
bfs()
print(board_cnt[100])딕셔너리를 이용하여 풀었다. 기본적인 접근자체는 비슷한거 같다. 근데 이렇게하면 처리를 각각해줘야 되니 귀찮을거 같다.
'취준 > 백준' 카테고리의 다른 글
| 16326 - 파이썬 (0) | 2022.08.02 |
|---|---|
| 1707 - 파이썬 (0) | 2022.08.02 |
| 1504 - 파이썬 (0) | 2022.07.27 |
| 7569 - 파이썬 (0) | 2022.07.26 |
| 7576 - 파이썬 (0) | 2022.07.14 |
