[백준] 2479번: 경로 찾기

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

2479번: 경로 찾기

문제 이해

해밍거리가 1이란 주어진 두 개의 코드 중에 하나의 비트만 다른 관계를 뜻한다.

 

코드 A 부터 B 까지 가장 짧은 경로를 찾는다. 따라서 BFS를 이용한다.

움직이는 것은 해밍 거리가 1인 관계에서만 가능하다.  

해밍 거리를 판단하는 것은 별도의 함수 (isHamming)로 구현해주었다.

 

단 BFS 를 이용할 때, 그 경로를 저장하는 것이 어렵다. 이를 위해 별도의 배열을 선언하여, 현재 방문한 노드의 전 노드가 무엇이었는지를 표시(path 배열)해둔다. (path[i] 는 i번째 노드에 도착하기 전 노드이다)

B에 도착하면 BFS는 종료한다. 

(BFS이므로 B에 제일 처음으로 도착한 그 순간이 최단 경로이다)

 

마지막으로 답안(경로)을 프린트할 때 path를 뒤에서부터 쫓아가며 프린트한다.

작성 코드 (C)

#include <stdio.h>

int N, K; // 코드 개수, 코드 길이
char code[1000 + 10][30 + 5];
int visited[1000 + 10];
int path[1000 + 10];
int A, B;

typedef struct ele {
    int idx;
    int time;
}ELE;

ELE q[100 * 100 + 10];
int rp, wp;

void enq(int idx, int time) {
    q[wp].idx = idx;
    q[wp].time = time;
    wp++;
}

ELE deq() {
    ELE tmp = q[rp];
    rp++;
    return tmp;
}

int isEmpty() {
    return rp == wp;
}

int isHamming(int a, int b) {
    int cnt = 0;
    for (int i = 0; i < K; i++) {
        if (code[a][i] != code[b][i]) cnt++;
        if (cnt > 1) return 0;
    }
    return 1;
}

int BFS(void) {

    enq(A, 1);
    visited[A] = 1;

    while (!isEmpty()) {
        ELE cur = deq();
        if (cur.idx == B) {	// 도착
            return cur.time;	// 몇 단계를 거쳤는지 return
        }
        for (int i = 1; i <= N; i++) {
            if (cur.idx == i) continue;
            if (visited[i] != 0) continue;	// 이미 방문한 코드

            if (isHamming(cur.idx, i)) {
                // 해밍 거리에 있는 친구이면
                visited[i] = 1;	// 방문
                path[i] = cur.idx;	// 경로에 전 노드 저장
                enq(i, cur.time + 1);	// 큐에 push해서 다음 경로 확인
            }
        }
    }
    return 0;
}

int main(void) {

    int res, k;
    int ans[1000 + 10];
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) {
        scanf("%s", &code[i]);
    }
    scanf("%d %d", &A, &B);

    res = BFS();
    
    if (res == 0) printf("-1");
    k = B;
    for (int i = 0; i < res; i++) {
        ans[res-1-i] = k;
        k = path[k];
    }
    
    for (int i = 0; i < res; i++) {
        printf("%d ", ans[i]);
    }

    return 0;

}

마지막에 path에 저장된 경로를 따라 B에서부터 거슬러 올라간다. 거슬러 올라가면서 별도 배열에 저장해서 방문 순서대로 출력할 수 있도록 한다.