exponential_e   5년 전

문제의 예제나 아래 게시글에 존재하는 반례는 다 잘 돌아가는데요.. 생각하는 방법이 잘못된건지 제출하자마자 틀렸다고 뜨네요.

우선 제가 생각한 아이디어는 간략히 말씀드리면,

  1. 화산이 존재하는 지역은 가지못함 -> 입력시 isRed = true로 초기화
  2. BFS로 움직이며 isVisited 배열을 통해 매 시간을 저장합니다.
  3. 이 배열에 저장된 값으로 경과된 시간을 참고하여 화산이 폭발 했는지 여부에따라 화산 쇄설류를 뿌려 줍니다.(이미 가지 못하는곳을 제외한 지역을 isRed = true로)
  4. 이렇게 작동하다 최대로 갈수 있는 높이를 저장하고 너비우선탐색이 종료시 해당 높이를 가지는 isVisited 배열에서 가장 작은 숫자를 받아옵니다.
  5. 이 가장 작은 숫자가 최소 시간이 됩니다. 출력: 최대 높이 + " " + 최소 시간

이렇게 풀었습니다. (아래 코드와 설명 다시 첨부 드리겠습니다.)

우선 조금 걸리는게 화산 쇄설류가 덮치는 타이밍을 잘못생각한 것(제가 생각한대로 덮치고 이동시키는게 맞나요..)인가 싶기도 하구요..

입력 1

1 3 1

1 3

50 40 30

1 1 1

출력 1

40 1

입력 2

1 3 1

1 3

50 40 30

1 1 0

출력 2

30 0 

이러한 입력에대해 각각의 출력값이 제대로 나오는게 맞는지도 궁금합니다. 읽어주셔서 감사합니다.

hello70825   5년 전

입력1, 입력2는 제 코드 출력과 일치합니다.

반례드립니다

https://ideone.com/REYmGB

최소 시간을 구하는 부분이 잘못되었나 봅니다.

exponential_e   5년 전

아 입력 1, 2가 같다니 그나마 다행이네요 ㅠㅠ

최솟값이 음수가 나오는 것을 보니.. ㅠㅠ 반례 감사드립니다!! 고민 더 해볼게요 ㅎㅎ

exponential_e   5년 전

반례주신 덕에 어렵지 않게 찾았습니다.ㅎㅎ

방문하지 않은 배열에 대해선 최소 시간을 가져오면 안되는 거였는데.. 이런실수를 하네요 ㅠㅠ

hello70825님 정말 감사드립니다.

덕분에 맞았습니다 ㅠㅠ

skynet0149   5년 전

hello70825 질문이 있습니다.

반례에서 시간이 -1이던데... 음수인 경우는 어떤 경우죠?


hello70825   5년 전

getMinTime과정에서 윤재상이 방문하지 않은 배열의 값도 포함하게 되어 그런 것 같습니다.

exponential_e   5년 전

hello70825님 말씀대로 

여기 7번째 줄에서 조건을 제대로 확인하지 않아서 접근하지 않은 위치 

즉, 방문배열 값이 0인 곳을 접근하게 되었고 따라서 -1(0 - 1) 값을 반환해 오답이 발생했습니다.

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