백준 16928 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으www.acmicpc.net

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

간단한 dfs문제이다.

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

주의할 점은 단 하나이다.

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

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

import sysfrom collections import dequeinput=sys.stdin.readlinedef 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]=bfor _ in range(m):
    a,b=map(int,input().split())    snake[a]=bbfs(1)