백준 16928 뱀과 사다리 게임

https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

처음에 멍청하게 배열을 만들어서 풀려했다 ㅋㅋㅋㅋ

 

간단한 dfs문제이다.

하필이면 kdt시간에 푸느라 엄청 안풀렸는데, 집에서푸니 10분컷이였다.

 

주의할 점은 단 하나이다.

뱀과 사다리는 무조건 타야 하므로

조건문을 제대로 설정해서, 타지 않은 경우를 큐에 넣지 않도록 주의하자

 

import sys
from collections import deque
input=sys.stdin.readline

def bfs(start=1):
    que=deque()
    que.append(start)
    arr[start]=0

    while que:
        now=que.popleft()
        
        for i in range(1,7):
            next=now+i
            if next==100:
                print(arr[now]+1)
                
                exit()
            

            elif next<=100 and arr[next]==-1:
                arr[next]=arr[now]+1
                if next in ladder :
                    if arr[ladder[next]]==-1:
                        arr[ladder[next]]=arr[next]
                        que.append(ladder[next])
                elif next in snake :
                    if arr[snake[next]]==-1:
                        arr[snake[next]]=arr[next]
                        que.append(snake[next])
                else:
                    que.append(next)


                




ladder={}
snake={}
arr=[-1 for _ in range(101)]
n,m=map(int,input().split())
for _ in range(n):
    a,b=map(int,input().split())
    ladder[a]=b
for _ in range(m):
    a,b=map(int,input().split())
    snake[a]=b

bfs(1)