whdnjqls456   4년 전

아.. 어디가 틀린지 도저히 모르겠습니다.


둘이 같은 숫자가 주어질 경우,

목적층 밑에서 -> 올라가서 만족시킬 경우,

목적층을 지나쳐 다시 되돌아올 경우,


셋다 고려한 것 같은데.. 계속 오류가 나네뇨 ㅠ; 고수님들 도움을 청합니다.

ehddml3   4년 전

일단 Ans를 DFS 들어가기 전에 1e9정도로 초기화 해야하구용(질문자님이 코드를 잘못 올린거 같긴하지만 여튼 이 코드에서는 초기화 안해서 예제가 안돌아가용)

그리구 최대 층이 1000000이기 때문에 visit 크기를 1000001로 해야할 것 같네용

whdnjqls456   4년 전

아!!!!!!!!!!!!!!!!!!!! 정말 감사합니다! 


이걸 놓치다니 ehddml3님의 통찰력에 감탄합니다 ^^ .


통과소스는 올려놓습니다.

#include <stdio.h>
int visit[1000001];
int Ans= 1000001;
int bool;
int isAllFloor, isGangHo, isObj;
int Up, Down;

// 층수 1~최대층인지 체크
int safe(int Value)
{
return (Value >= 1 && Value <= isAllFloor);
}

void DFS(int local, int count)
{
if (local == isObj)
{
// 최소값을 찾는 것이기 때문에 계속 최솟값 찾기.
if (Ans > count)
Ans = count;
bool = 1;
return;
}

// 시간을 줄이기 위한 visit체크
visit[local] = 1;

// 1~최대층 사이에 해당되고, 방문하지 않았다면 방문.
if (safe(local + Up) && visit[local + Up] == 0)
DFS(local + Up, count + 1);

if (safe(local - Down) && visit[local - Down] == 0)
DFS(local - Down, count + 1);

return;
}

int main()
{
scanf("%d%d%d%d%d", &isAllFloor, &isGangHo, &isObj, &Up, &Down);

// 만약 목적층이랑 같은 층이라면 0출력하고 끝
if (isGangHo == isObj)
{
printf("0\n");
return 0;
}

// 아니라면 DFS
DFS(isGangHo, 0);

if (bool)
printf("%d\n", Ans);
else
printf("use the stairs\n");

return 0;
}

댓글을 작성하려면 로그인해야 합니다.