728x90
https://www.acmicpc.net/problem/27211
조금 지저분하게 푼 것 양해바랍니다,,
우선, 보드의 크기와 입력은 고정되어있으므로 선언해준 뒤 시작한다. 이때 10x10 이라고 무조건 2차원 배열로 만들 필요는 없다!
주사위는 +1 ~ +6까지 무조건 양의 방향으로만 증가하므로 1차원 배열로 선언해주어야 더 쉽게 풀 수 있다.
사다리와 뱀의 정보도 구별 지을 필요 없다. 어찌됐건 둘 다 만나면 다른 곳으로 이동하므로 하나의 리스트에 "이동 정보" 를 모두 저장해주었다.
그리고 보드의 인덱스 하나에는 하나의 값이 아닌, [현재 위치, 만약 사다리나 뱀이 있다면 이동할 위치] 를 쌍으로 저장해주었다.
이제 bfs를 돌면 된다. bfs의 기본적인 틀에서 크게 벗어나는 것은 없다. 그저 jump할 곳이 있다면 그곳으로 jump 해주면 된다.
import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline
board = [0] + [ [i,0] for i in range(1,101)]
num = 1
ladder = []
visited = [False for _ in range(101)]
dx = [1,2,3,4,5,6]
def bfs():
q = deque()
q.append([1,0])
visited[1] = True
cnt = 0
while q:
x = q.popleft()
cnt = x[1]
if x[0] == 100:
return cnt
for i in range(len(dx)):
nx = x[0] + dx[i]
if nx > 100: continue
jump = int(board[nx][1])
if jump != 0 and not visited[jump]:
q.append([jump,cnt+1])
visited[jump]= True
elif jump == 0 and not visited[nx]:
q.append([nx,cnt+1])
visited[nx]= True
n,m = map(int,input().split())
for i in range(n+m):
x,y = map(int,input().split())
ladder.append([x,y])
for i in range(1,101):
for j in range(n+m):
if ladder[j][0] == board[i][0]:
board[i] = [num,ladder[j][1]]
print(bfs())
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 13023번 ABCDE (0) | 2023.01.25 |
---|---|
[백준/파이썬] 4673번 셀프 넘버 (0) | 2023.01.25 |
[백준/파이썬] 12100번 2048 (0) | 2023.01.16 |
[백준/파이썬] 13904번 과제 (0) | 2023.01.10 |
[백준/파이썬] 2225번 합분해 (0) | 2023.01.09 |