c언어 5014번 스타트링크 (백준)

#include <stdio.h>

int main(void)
{
	int f, s, g, u, d;
	scanf("%d %d %d %d %d", &f, &s, &g, &u, &d);
	
	int visit[f+1];
	for(int i = 0; i<=f; i++) visit[i] = 0;
	int q[1000001];
	int qcnt = 0;
	int ans[1000001] = {0};
	int acnt = 0;
	int ptr = 0;
	
	ans[acnt] = 1;
	q[qcnt++] = s;
	visit[s] = 1;
	
	while(1)
	{
		if(ptr == qcnt) break;
		if(q[ptr] == g) {
			printf("%d", acnt);
			return 0;
		}
		if(q[ptr] + u <= f && visit[q[ptr] + u] == 0) {
			ans[acnt+1]++;
			visit[q[ptr] + u] = 1;
			q[qcnt++] = q[ptr] + u;
		}	
		
		if(q[ptr] - d > 0 && visit[q[ptr] - d] == 0) {
			ans[acnt+1]++;
			visit[q[ptr] - d] = 1;
			q[qcnt++] = q[ptr] - d;
		}
		ptr++;
		if(--ans[acnt] == 0) acnt++;
	}
	printf("use the stairs");
	return 0;
}

5014번: 스타트 링크 (acmicpc.net)

5014번: 스타트링크

 

풀이 ( BFS 이용)

0) 한 번 지나간 층은 다시는 지나가지 않으므로 (최소한의 횟수로 g을 가야 하기 때문이다)

   visit[] 배열을 통해 다시 지나가는 것을 방지해 준다.

1) 1~f 의 범위 내에서 u만큼 증가, 또는 d만큼 감소시킨다.

2) 1) 과정 중에, g에 도달하게 되면 그 즉시 bfs을 종료한다.

3) 2)을 만족시키지 못하고, 큐에 아무것도 남지 않게 되면 (ptr == qcnt) ,

    BFS을 종료하고 use the stairs을 출력한다.

 

위 코드에서의 BFS 설명 (야매로 만든 BFS)

 

q[] : queue 말 그대로 큐

qcnt : 큐의 크기, 하나가 들어올 때마다 1씩 증가

 

ans[] : BFS에서의 층(?)마다 몇 개의 노드가 있는지를 담는 배열

acnt : BFS에서의 층(?)을 나타냄

 

ex) 1 -> 2 -> 3

                -> 4

      여기서 3, 4는 두 번째 층

 

코드에서 if(--ans[acnt] == 0) acnt++;

을 통해 층에 있는 모든 노드를 지나가면 층을 내려간다.

 

visit[] : 방문 안 했다면 0, 그렇지 않으면 1

 

ptr : BFS에서 큐를 차례차례 살펴보기 위한 변수