코드

from collections import deque
n, m = map(int, input().split())

# 사다리와 뱀은 같은 칸에 있을 수 없다 했으므로
# 그냥 하나의 리스트로 관리
ls = [0 for _ in range(101)]

# 사다리의 위치
for _ in range(n):
    x, y = map(int, input().split())
    
    ls[x] = y
    
# 뱀의 위치    
for _ in range(m):
    u, v = map(int, input().split())
    
    ls[u] = v

# 방문 여부 체크 리스트    
visited = [False] * (101)

# 각 보드까지의 이동 횟수를 담을 변수
cnt = [0] * 101

def game(x, visited):
    q = deque()
    q.append(x)
    
    # 1번에서 시작
    visited[1] = True
    
    while q:
        start = q.popleft()
                
        # 주사위를 굴림
        for i in range(1, 7):
            
            # 주사위로 이동한 다음 위치
            _next = start + i

            # 범위가 넘어버리면 반복 무시
            if _next < 1 or _next > 100:
                continue

            # 방문한 적 없는 위치일 때
            if not visited[_next]:
                
                # 현재 이동한 위치의 값에 
                # 뱀이나 사다리가 없지 않다면
                # ls의 값이 0인 경우 => 뱀도 사다리도 없다
                if ls[_next] != 0:
                    
                    # 연결된 곳의 좌표로 값을 바꿈
                    # 즉, 사다리나 뱀을 타고 이동한 위치가 됨
                    _next = ls[_next]  

                # 다음 위치도 방문한 적이 없다면
                if not visited[_next]:
                    
                    # 방문 처리하고 큐에 넣어줌
                    visited[_next] = True
                    q.append(_next)
                    
                    # 최종적으로 도착한 곳
                    # => 주사위 1회 던져서 도착한 곳
                    cnt[_next] = cnt[start] + 1    
                    
game(1, visited)

# 100번째 칸에 몇번 만에 도착했는가
print(cnt[100])

문제 해설

도착 지점에 갈 수 있는 최소 횟수를 구하라는 부분에서 BFS라는 힌트를 얻어 문제에 접근하였다.

문제 자체에 대한 이해는 굳이 그림을 그리면서 할 필요는 없어서 그림은 생략하고 주석과 아래로 대신한다.

뱀과 사다리 게임

위와 같이 문제 풀이에 필요한 부분을 정리하고 풀이를 시작했는데 다른 건 다 스무스하게 진행됐으나 최종적으로 구해야하는 최소 도달 횟수를 어떤식으로 받아서 처리해야 하는지 감을 잡지 못했다ㅠㅠ. 한참을 고민하다가 약간의 힌트를 얻은 방법은 횟수를 담을 리스트를 별도로 생성해서 관리해주는 방법이었다. 다양한 문제를 많이 풀어보면서 이런 힌트 없이도 확실하게 문제를 풀 수 있도록 성장해야겠다ㅠㅠ

댓글남기기

참고