[Python][C++] 16928번 뱀과 사다리 게임

문제

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

 

 

 

 

코드

1. Python

import sys
from collections import deque

input = sys.stdin.readline  # 빠른 입력을 위해 sys.stdin.readline 사용

# BFS(너비 우선 탐색) 함수 정의
def bfs(v):
    visited = [0] * 101  # 방문 여부와 이동 횟수를 저장할 리스트 (0~100까지, 총 101칸)
    visited[v] = 1  # 시작점인 1번 칸은 방문했으므로 1로 설정

    q = deque()  # 탐색에 사용할 큐 생성
    q.append(v)  # 시작점(1번 칸)을 큐에 삽입

    # 큐가 빌 때까지 BFS 탐색 진행
    while q:
        v = q.popleft()  # 큐에서 현재 위치를 꺼냄

        # 주사위를 1~6까지 굴려서 이동 가능한 모든 경우를 확인
        for i in range(1, 7):
            nv = v + i  # 주사위 굴려서 나온 칸 번호

            # 주사위를 굴려 나온 칸이 100 이하이며 아직 방문하지 않았을 경우
            if nv <= 100 and not visited[nv]:
                visited[nv] = visited[v] + 1  # 이동 횟수를 기록

                nnv = board[nv]  # 뱀 또는 사다리로 인해 이동할 수 있는 칸
                if board[nv]:  # 뱀이나 사다리가 있는 경우
                    if not visited[nnv]:  # 해당 칸으로 이동한 적이 없으면
                        visited[nnv] = visited[nv]  # 이동 횟수 동일하게 기록
                        q.append(nnv)  # 그 칸을 큐에 추가
                else:
                    q.append(nv)  # 뱀이나 사다리가 없으면 그냥 이동한 칸을 큐에 추가

    return visited[100]  # 100번 칸에 도달했을 때의 이동 횟수 반환

# 사다리와 뱀의 개수 입력 (n: 사다리 수, m: 뱀 수)
n, m = map(int, input().split())

board = [0] * 101  # 보드 초기화 (1~100까지의 칸, 0: 기본 상태, 특정 숫자: 이동해야 할 칸)
for _ in range(n + m):  # 사다리와 뱀 정보를 입력받아 보드에 반영
    start, end = map(int, input().split())
    board[start] = end  # 사다리나 뱀의 시작 칸에 도착할 목적지를 기록

# bfs를 사용하여 1번 칸에서 100번 칸으로 가는 최소 이동 횟수를 계산 후 출력
print(bfs(1) - 1)  # 방문 횟수를 1부터 시작했으므로 결과에서 1을 뺌

 

2. C++

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<int, int> mp;  // 사다리와 뱀의 위치를 저장하는 맵

// BFS 함수: 시작 지점 v에서 100까지의 최소 이동 횟수 계산
int bfs(int v) {
	queue<int> q;  // BFS 탐색을 위한 큐
	vector<int> visited(101);  // 방문 여부와 이동 횟수를 저장하는 배열 (1부터 100까지)

	q.push(v);  // 시작점 1을 큐에 넣음
	visited[v] = 1;  // 시작점은 방문 처리, 이동 횟수를 1로 설정

	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		v = q.front();  // 큐의 첫 번째 요소를 가져옴
		q.pop();  // 큐에서 제거

		// 100번 칸에 도착하면 이동 횟수를 반환
		if (v == 100)
			return visited[v] - 1;  // 처음 시작을 1로 설정했으므로 -1

		// 주사위 1부터 6까지의 값을 더하여 새로운 위치 계산
		for (int i = 1; i <= 6; i++) {
			int nv = v + i;  // 새로운 위치

			// 새로운 위치가 100을 넘어가면 무시
			if (nv > 100)
				continue;

			// 새로운 위치에 사다리나 뱀이 있다면 이동
			if (mp[nv]) {
				nv = mp[nv];  // 사다리 또는 뱀을 타고 이동
			}

			// 방문하지 않은 위치라면 큐에 추가
			if (!visited[nv]) {
				q.push(nv);  // 새로운 위치를 큐에 추가
				visited[nv] = visited[v] + 1;  // 현재 위치까지의 이동 횟수 + 1
			}
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;  // 사다리의 수 n, 뱀의 수 m 입력

	// 사다리의 시작과 끝을 맵에 저장
	while (n--) {
		int x, y;
		cin >> x >> y;
		mp[x] = y;  // x 위치에서 y 위치로 이동하는 사다리
	}

	// 뱀의 시작과 끝을 맵에 저장
	while (m--) {
		int u, v;
		cin >> u >> v;
		mp[u] = v;  // u 위치에서 v 위치로 이동하는 뱀
	}

	cout << bfs(1);  // 1번 칸에서 시작하여 100번 칸까지의 최소 이동 횟수 출력

	return 0;
}

 

 

풀이

 

1. 그래프 탐색:
   • 보드를 하나의 그래프로 보고 각 칸을 정점으로 간주한다.
   • 주사위를 굴릴 때 1부터 6까지 이동할 수 있으며, 사다리나 뱀이 있는 칸에 도착하면 해당 칸으로 즉시 이동하게 된다.
   • 최단 경로를 찾는 문제이므로 BFS를 사용하여 최소한의 주사위 굴림 수를 구할 수 있다.
2. BFS 구현:
   • 시작점은 1번 칸이며, 큐를 이용해 BFS를 진행한다.
   • 현재 칸에서 주사위를 굴려 1부터 6까지의 값을 더한 칸으로 이동한다. 이동한 칸이 사다리나 뱀이 있는 경우 해당 위치로 즉시 이동한다.
   • 이미 방문한 칸은 다시 방문하지 않도록 처리하여 중복 탐색을 방지한다.
3. 방문 배열:
   • 각 칸에 도달하는 최소 주사위 굴림 수를 저장하는 배열을 사용하여 BFS 진행 중에 업데이트한다.
   • BFS가 완료되면 100번 칸에 도달하는 최소 주사위 굴림 수를 출력한다.
4. 사다리와 뱀 처리:
   • 주어진 사다리와 뱀의 정보를 미리 배열에 기록하여, 해당 칸에 도달할 때 이동할 수 있도록 한다.