3-I 질문있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-I

작성

110

http://boj.kr/5c6791ecb33241cab42be762031958c3

안녕하세요 큰돌님

이번 문제는 강의를 봐도 잘 이해가 되지 않아서 핵심으로 짚어준 부분을 참고하여 제가 로직을 구현했는데, 어려움이 있어 질문드립니다.

백준 문제에서 주어진 예제는 정답이 나오는데, 아래 링크의 질문 게시판에 있는 반례는 모두 틀리게 나옵니다.
https://www.acmicpc.net/board/view/89304

코드에 사용되는 변수는 다음과 같습니다.
x = bfs로 방문하는 수빈이의 현재 위치
t = 수빈이가 해당 위치에 도착하는 최단 시간
bp = 해당 시간(t)에 동생의 현재 위치

제가 생각해낸 방법은 다음과 같습니다.

먼저 동생이 앞으로 가며 위치에 도달하는 시간을 brother[] 배열에 기록했습니다.
수빈이가 동생을 만날 수 있는 방법을 다음 두 가지로 분류했습니다.
(1) 수빈이가 앞으로 가며 특정 위치에서 동생과 만난다.
(2) 수빈이가 동생보다 먼저 앞으로 간 다음에, 왔다갔다 하며 동생을 기다린다. (이 때 홀수, 짝수 시간으로 동생과 만날 수 있는지 확인한다.)
bfs를 단계 별로 구현하기 위해 5분 45초에 나오는 플루드 필(?)을 수빈이가 해당 위치에 도착하는 최단 시간(변수 t)로 구현하였습니다.

제 코드의 오류를 하나 발견하였는데 다음과 같습니다.
예제 n = 18, k = 66 를 넣었을 때,
수빈이는 18 36 37 38 76 순으로 방문하고, 동생이 66, 67, 69, 72, 76 순으로 방문 했을 때 정답인 4초가 나오지만, 제 코드 상으로는 76을 최단 시간인 3초에 방문할 수 있으므로, 수빈이가 동생을 만나지 못한다고 판단하여 만날 수 있는 다음 지점을 답으로 출력합니다.

위와 같은 오류를 어떤 논리로 잡아야 할지 아무리 생각해도 모르겠고, 강사님의 코드도 도저히 이해가 가지 않아 질문 드립니다. ㅠㅠ

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 무성님 ㅎㅎ

제 코드 상으로는 76을 최단 시간인 3초에 방문할 수 있으므로, 수빈이가 동생을 만나지 못한다고 판단하여 만날 수 있는 다음 지점을 답으로 출력합니다.

똑같은 지점에 수빈이는 홀수로 방문할 수 있고 짝수로 방문할 수 있는데 이부분에 대한 반례가 생긴 것 같습니다.

해당부분을 위해서는 2차원을 사용해야 합니다.

            if (visited[next] == 0)
            {
                visited[next] = visited[x] + 1;

이 로직 만으로는 해당 부분을 처리하지 못합니다.

솔직히 1차원 visited를 쓰다 2차원 visited를 쓰는게 어색할 수 있는데요. ㅎㅎ

이렇게 생각하시면 됩니다.

예를 들어 3이라는 정점에 10초에 수빈이가 방문했고, 11초에 방문했음을 처리하려면 어떻게 해야할까?

그 이후 동생이 12초 또는 13초에 방문했다면 이는 서로 만날 수 있는 건데... 이를 처리하려면 어떻게 해야할까?

3이라는 정점 = visited[3]에다가

[홀수]에 방문

[짝수]에 방문.

이 2가지 경우의 수가 있기 때문에

visited[3][0] = 짝수일 때 방문

visited[3][1] = 홀수일 때 방문

으로 놓자고 하여 2차원배열을 쓰게 되는 것입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

신무성님의 질문을 검토한 결과, 수빈이와 동생이 만나는 조건 및 로직 구현에 관한 이해와 관련하여 유사한 고민과 질문이 있는 게시물을 찾았습니다. 이에 따라 다음의 답변 링크를 드립니다. 해당 답변들은 수빈이와 동생이 만나는 조건을 구현하는 방법과, 홀수와 짝수 시간의 개념을 사용하는 방법에 대한 통찰을 제공합니다.

“3-I 17071번 숨바꼭질 5 질문있습니다.”에서는 수빈이가 원하는 시간에 도달해 동생과 만날 수 있는 조건의 구체적인 구현에 대한 설명이 담겨 있습니다. 특히, 동생의 위치 도달 시간과 홀수, 짝수 개념의 활용에 초점을 둔 해설이 제공되어 있습니다.
“3-I 17071 문제 질문있습니다.”에서는 배열을 활용한 알고리즘의 구현 방식과 관련해 구체적인 설명과 함께 답변을 제공하고 있으며, 홀수와 짝수를 구분하여 문제를 해결하는 전략에 대한 깊이 있는 논의를 볼 수 있습니다.

위 두 링크에서는 문제를 푸는 중요한 아이디어인 시간을 홀수, 짝체로 나누어 이해하고 구현하는 방법에 대한 설명이 포함되어 있어, 신무성님의 현재 질문에 대한 해결책을 찾는 데 도움이 될 것으로 보입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

3-I 질문있습니다.