BOJ 14496 · 그대, 그머가 되어

알고리즘 분류 : BFS  

야민정음을 통해 A 문자를 B 문자로 치환할 때, 최소 치환 횟수를 구하는 문제다. 인접 리스트 기반의 BFS 문제로 보면 된다.

• 입력으로 주어지는 치환 문자쌍을 인접 리스트로 만든다.
• 문자 A부터 BFS 탐색을 시작하여 문자 B까지 도달하는 최소 횟수를 구하면 된다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int a, b, n, m;
vector<int> v[1001];
int dist[1001];

void bfs() {
    queue<int> q;
    q.push(a);
    dist[a] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (x == b) {
            printf("%d\n", dist[x]);
            return;
        }
        for (int nx : v[x]) {
            if (dist[nx] == -1) {
                q.push(nx);
                dist[nx] = dist[x]+1;
            }
        }
    }
    printf("-1\n");
}

int main() {
    memset(dist, -1, sizeof(dist));
    scanf("%d %d", &a, &b);
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bfs();
    return 0;
}

---

Python 3 소스코드

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

def bfs():
    q = deque()
    q.append(a)
    dist[a] = 0
    while q:
        x = q.popleft()
        if x == b:
            print(dist[x])
            return
        for nx in v[x]:
            if dist[nx] == -1:
                q.append(nx)
                dist[nx] = dist[x]+1
    print(-1)

a, b = map(int, input().split())
n, m = map(int, input().split())
v = [[] for _ in range(n+1)]
dist = [-1]*(n+1)
for i in range(m):
    x, y = map(int, input().split())
    v[x].append(y)
    v[y].append(x)
bfs()

---

참고

• 백준 온라인 저지 : BOJ 14496