2479번 경로 찾기

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

인접행렬을 만든뒤에  BFS 돌리면 된다.  BFS문제를 오랜만에 풀어서그런지 너무 코드가 더럽다.

요로코롬 인접행렬만들기

#include<stdio.h>

#define A 1001

char arr[A][31];

int map[A][A], min=1001, N, K, start, stop, Q[A][3],check[A][A],count;

int min_last,root[A],root_count;

void BFS()

{

int bun = 1, work = 0;  // Q[][0] 에는 인접행렬    Q[][1] 에는 이동 횟수

Q[1][0] = start;

while (1)

{

if (bun == work) break;

work++;

for (int i = 1; i <= N; i++)

{

if (map[Q[work][0]][i] == 1 && i != start && check[Q[work][0]][i] == 0)

{

bun++;

check[Q[work][0]][i] = 1;

check[i][Q[work][0]] = 1;

Q[bun][0] = i;

Q[bun][1] = Q[work][1] + 1;

Q[bun][2] = work;

}

if (Q[bun][0] == stop)

{

if (Q[bun][1] < min)

{

min = Q[bun][1];

min_last = bun;

}

}

}

}

}

int main()

{

scanf("%d %d", &N, &K); // N : 코드 수 ,  K : 코드 길이

for (int i = 1; i <= N; i++) // 코드 입력

scanf("%s", &arr[i]);

scanf("%d %d", &start, &stop); // start : 시작위치 , stop : 도착위치 

for (int i = 1; i <= N; i++)

{

for (int j = 1; j <= N; j++)

{

for (int k = 0; k < K; k++)

{

if (arr[i][k] != arr[j][k])

count++;

}

if (count == 1)

map[i][j] = 1;

count = 0;

}

}

BFS();

while (1)

{

root[root_count] = Q[min_last][0];

min_last = Q[min_last][2];

if (min_last == 0)

break;

root_count++;

}

if (min == 1001)

printf("-1");

else

{

for (int i = min; i >= 0; i--)

printf("%d ",root[i]);

}

return 0;

}