[BOJ] 백준 2479 경로 찾기

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

 Input 

5 3

000

111

010

110

001

1 2

　 

 Output 

1 3 4 2

① src → dest로 가는 최단 경로를 BFS 탐색

② BFS 조건은 아래와 같습니다.

    - 자기자신 제외

    - vistied[] 배열로 더 좋은 최단거리

    - 해밍 거리 = 1인 경우

      ※ [BOJ] 3449 해밍 거리는 문자열과 xor 연산을 이용해서 처리

 

③ 경로 추적할 때는 trace[y] = x를 이용합니다.

      : y 지점을 방문하기 위해 바로 직전에 지점 x

    재귀함수로 역추적하며 도착점에서 출발점까지 거슬러 찾아갑니다.

---

#include <stdio.h>
 
const int MAX_N = 1000;
const int MAX_K = 30;
const int INF = 2e9;
 
struct Node {
    int pos, distance;
}que[MAX_N * MAX_N];
int visited[MAX_N + 5];
int fr, re;
int N, K, src, dest;
char str[MAX_N + 5][MAX_K + 5];
int trace[MAX_N];
 
int len(const char *str) {
    int ret = 0;
    for (;;) {
        if (str[ret++] == '\0') break;
    }
    return ret;
}
 
int findHamming(const char *a, const char *b) {
    int ret = 0;
    for (int i = 0; i < len(a); ++i) {
        if ((a[i] - '0') ^ b[i] - '0')
            ret++;
    }
    return ret;
}
 
void BFS() {
    for (int i = 1; i <= N; ++i) {
        visited[i] = INF;
    }
 
    que[re++] = { src, 0 };
    visited[src] = 0;
 
    while (fr < re) {
        Node cur = que[fr++];
        
        if (cur.pos == dest) continue;
        for (int i = 1; i <= N; ++i) {
            // 자기 자신 제외
            if (cur.pos == i) continue;
            
            int nextDistance = cur.distance + 1;
            if (visited[i] <= nextDistance) continue;
 
            if (findHamming(str[cur.pos], str[i]) != 1) continue;
            visited[i] = nextDistance;
            trace[i] = cur.pos;
            que[re++] = { i, nextDistance };
        }
    }
}
 
void printTrace(int p) {
    if (p == 0) return;
    printTrace(trace[p]);
    printf("%d ", p);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; ++i) {
        scanf("%s", str[i]);
    }
    scanf("%d %d", &src, &dest);
    
    BFS();
    if (visited[dest] == INF) printf("-1");
    else printTrace(dest);
}