정올 경로찾기
길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들어, A=010010, B=011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다. 우리는 총 N개의 이진 코드를 가지고 있고, 각 코드의 길이는 K로 같다. 예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다. A=000, B=111, C=010, D=110, E=001 두 코드 사이의 해밍 거리를 H(A,B)로 표현한다. 그러면, H(A,B)=3, H(A,C)=1, H(A,D)=2, H(A,E)=1 이다. 우리는 이진 코드들에 대해 해밍 경로를 찾고자 한다. 해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다. 위의 예에서 (A,C,D)는 코드 A와 C의 해밍 거리가 1이고, 코드 C와 D의 해밍 거리가 1이므로 해밍 경로이다. (A,E,B)는 코드 A와 E의 해밍 거리는 1이지만, 코드 E와 B의 해밍 거리가 2이므로 해밍 경로가 아니다. 이 문제는 주어진 두 코드 사이에 가장 짧은 해밍 경로를 구하는 프로그램을 작성하는 것이다. 입력 /* 5 3 100 111 010 110 001 1 2 */ |
나중에 재귀적으로 돌리기만 하면 됨.
#include <stdio.h>
int SERO;
int GARO;
int map[1010][32];
int tmp[32];
int check[32]; //가본곳
int START;
int END;
typedef struct {
int path[32];
int pastposition;
int step;
int idx;
}_pos;
_pos POSITION[10000];
int main(void)
{
// 여기서부터 작성
scanf("%d", &SERO);
scanf("%d", &GARO);
int i, j,k;
for (i = 0; i < SERO; i++)
{
for (j = 0; j < GARO; j++)
{
scanf("%1d", &map[i][j]);
}
}
scanf("%d", &START);
START--;
scanf("%d", &END);
END--;
int head = 0, tail = 1;
check[START] = 1;
for (i = 0; i < GARO; i++)
{
POSITION[0].path[i] = map[START][i];
}
while (1)
{
if (head == tail) break;
for (int dir = 0; dir < GARO; dir++)
{
// 하나씩 bit 를 바꿔봄
for (i = 0; i < GARO; i++)
{
tmp[i] = map[head][i];
}
tmp[dir] = !tmp[dir];
// 동일한게 있는지 search한다
int match = 1; // 0이 맞는게 없다는 뜻 1이 다 맞다는 거
for (i = 0; i < SERO; i++)
{
match = 1;
for (j = 0; j < GARO; j++)
{
if (tmp[j] != map[i][j])
{
match = 0;
}
}
if (match == 1 && i == END)// GOAL이 있다면 아웃
{
for (k = 0; k < GARO; k++)
{
POSITION[tail].path[k] = tmp[k];
}
POSITION[tail].pastposition = head;
POSITION[tail].step = POSITION[head].step + 1;
POSITION[tail].idx = i;
check[i] = 1;
printf("found!!");
goto out;
}
if (match == 1 && !check[i]) // 끝은 아니지만 연결은 되었다면
{
//queue에 넣어라
for (k = 0; k < GARO; k++)
{
POSITION[tail].path[k] = tmp[k];
}
POSITION[tail].pastposition = head;
POSITION[tail].step = POSITION[head].step + 1;
POSITION[tail].idx = i;
check[i]= 1;
tail++;
}
}
}
head++;
}
out:
printf("Aaa");
// 맨 마지막에 위치를 역으로 찾아가게만 하면 된다.
return 0;
}