백준) 1697번: 숨바꼭질 in C

Made with Stable Diffusion

Problem

1697번: 숨바꼭질

 

Solution

이 문제는 BFS를 통해 풀 수 있었다.

 

우선 BFS 는 큐라는 FIFO 식 자료구조를 이용해야 하는데 C++은 몰라도 C는 큐 기능을 제공하는 라이브러리가 없어서 프로그래머가 직접 구현해야한다는 단점이 있다. 이러한 문제점으로라도 C++을 빨리 배워야겠다는 생각이 든다.

 

먼저 점 N에서 시작하는 술래는 1초당

1) 뒤로 한 칸(X-1)

2) 앞으로 한 칸(X+1)

3) 2 *X 칸으로 순간이동

총 세 가지 action 중 하나를 취하게 된다.

 

이를 트리 구조로 나타낸다면 차수가 3인 트리가 된다.

그리고 앞서 말했듯 BFS를 통해 답을 찾는데 큐 자료구조가 사용된다.

 

먼저 N 을 큐에 집어넣고 visited에 1을 넣어서 이미 고려하였음을 표시한다.

그리고 큐에서 값을 가져오고 그 값(N)이 K와 다른 경우 N * 2, N - 1, N + 1 값을 각각 큐에 집어넣는다. 또한 각 값에 대해서 visited는 'N 값의 visited' + 1, 즉 2를 넣어준다. visited는 각 값을 고려하였음을 표시하는 목적도 있지만 최종 결과값, 즉 N이 K까지 가는데 걸리는 시간(초)를 구하는 목적도 있다. 이는 Tree의 Level과 같다.

 

다시 큐에서 값을 가져오고(여기서는 N * 2이지만 t 라고 하겠다) K와 비교한다. 다를 때 다시 t * 2, t -1, t +1, 값을 각각 큐에 집어넣고 visited도 알맞은 값을 넣는다.(t 값의 visited + 1, 즉 3)

 

위 과정을 반복한다. 그리고 K와 같은 값을 찾았을 경우 그 값의 visited - 1이 답이 된다. 처음 N값으로 시작할 때 visited가 1이었기 때문이다. (만약 N과 K가 같은 값이었을 때는 visited - 1는 1 -1, 즉 0초가 될 것이다.)

 

큐를 이용한 BFS 수도 코드는

N 큐에 삽입;
N 방문 표시 (visited[N] = 1);
while(1){
	큐에서 가져온 값(t)과 K 값 비교, 같을 시 break;
	t * 2, t - 1, t + 1 값을 각각 큐에 집어넣고 각 visited에 대해서 visited[t] + 1 입력;
}

visited[t] - 1 값 리턴;

이다.

 

다음은 N과 K가 각각 5와 17일 때 풀이과정을 그림으로 표현해보았다.

여기서 이미 visited 가 0이 아닌 값에 대해서는 큐에 집어넣지 않도록 하였다. (예를 들어, 5 -> 4-> 5 인 경우)

그리고 C언어의 경우, 처음 풀이시 Out Of Bounds 에러가 떴었다. t * 2나 t + 1가 다루는 값 중 미리 설정된 값의 범위를 넘어가서 생기는 이유이므로 100000보다 큰 값은 고려하지 않도록 조건문에 추가해줬다.

 

Code

#include <stdio.h>
#include <stdlib.h>

int N, K, sec = 0, visited[200001] = {0, };

typedef struct node{
	int data;
	struct node *next;
}NODE;

NODE *head, *tail;

void enqueue(int data){
	NODE *newnode = (NODE *)malloc(sizeof(NODE));
	newnode->data = data;
	newnode->next = NULL;
	
	if(head == NULL){
		head = newnode;
		tail = newnode;
	}
	else{
		tail->next = newnode;
		tail = newnode;
	}
};

int dequeue(){
	if(head == NULL)
		return -1;
	
	int tdata = head->data;
	NODE *tnode = head;
	
	head = head->next;
	free(tnode);
	
	return tdata;
};

int BFS(){
	enqueue(N);
	visited[N] = 1;
	int temp;
	
	while(1){
		temp = dequeue();
		if(temp == K)
			break;
		if(!visited[temp * 2] && temp * 2 <= 100000){
			enqueue(temp * 2);
			visited[temp * 2] = visited[temp] + 1;
		}
		if(!visited[temp - 1]){
			enqueue(temp - 1);
			visited[temp - 1] = visited[temp] + 1;
		}
		if(!visited[temp + 1] && temp + 1 <= 100000){
			enqueue(temp + 1);
			visited[temp + 1] = visited[temp] + 1;
		}
	}
	
	return visited[temp];
};

int main(){
	scanf("%d%d", &N, &K);
	
	printf("%d\n", BFS() - 1);
	return 0;
}

 

Final Comment

- 큐 같은 자료구조를 사용하기 위해서는 학습용으로는 몰라도 코테용으로 C는 부적절한 언어인 것 같다. C++를 배워봐야 겠다.