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

안녕하세요 ㅎㅎ

visited[1]은 bro[next]와 비교해서 나중에 조건 맞으면 찍는 방식인데

“최단 시간에 그 위치에 도착한 홀수 시간”이어야 합니다.

즉, visited[1]의 경우도 BFS에서 시간 홀짝 기준으로 채워서 최단거리를 만들어야 합니다.

예를 들어

어떤 위치 x에

2초에 도착 가능

4초에도 도착 가능

6초에도 도착 가능

할 수 있다고 해보겠습니다.

이건 왕복 이동 때문에 가능합니다. 예를 들어 x -> x+1 -> x처럼 2초를 더 써서 같은 위치에 다시 올 수 있습니다.

그래서 어떤 위치는 한 번 도착한 뒤에도 같은 홀짝 시간대로 계속 다시 도달할 수 있습니다.

그런데 중요한 것은 “홀수 시간에 처음 가능한 시각”과 “짝수 시간에 처음 가능한 시각”을 정확히 알아야 한다는 점입니다.

현재 코드의 논리는 대략 이런 거 같은데요.

visited[0][x]가 이미 있으면, 동생 시간 bro[x]와의 차이가 짝수인지 보고 그 시간에도 있을 수 있다고 치자.

이 아이디어 자체는 방향은 맞는 부분이 있습니다.

한 번 도착한 뒤 2초씩 소모해서 제자리에 다시 올 수 있으니까요.

하지만 문제는 그걸 visited[1]에 채우는 방식이 BFS 상태 전이와 전혀 맞지 않는다는 점입니다.

왜냐하면 visited[1][x]는 원래

“홀수 시간에 x에 도착하는 최소 시간”

이어야 하는데, 지금 코드는

“동생이 x에 오는 시간과 우연히 맞으면 그 시간으로 기록”

해버립니다.

즉 visited[1]이 수빈이의 실제 최단 도달 시간 배열이 아니라, 동생 스케줄에 종속된 보정 배열이 되어버립니다.

이러면 어떤 문제가 생기냐면 다음과 같습니다.

첫째, 어떤 위치에 홀수 시간으로 더 빨리 갈 수 있어도 그 정보가 전파되지 않습니다.

BFS에서는 예를 들어 3초에 x 도착이 있으면 거기서 다음 상태들인 4초의 x-1, x+1, 2x가 퍼져나갑니다.

그런데 지금 방식은 visited[1][x]를 나중에 찍기만 하고, 그 상태에서 다시 다음 칸으로 탐색을 이어가지 않습니다.

즉 홀수 시간 상태를 “도달 가능한 상태”로 취급하지 않기 때문에

홀수 시간 상태를 기반으로 만들어지는 다음 최단 경로들이 전부 누락되서 틀립니다.

둘째, visited[1][x]의 값이 최단이라는 보장이 없습니다.

BFS로 채운 배열은 큐 순서 때문에 처음 방문한 시각이 최단입니다.

하지만 지금은 bro[next]와 비교해서 특정 시간으로 박아버리므로, 그 시간이 정말 수빈이가 홀수 시간으로 next에 도달하는 최소 시각인지 보장되지 않습니다.

그래서 틀린 것 같습니다. (나머지 부분은 다 잘짜셨어요 ㅎㅎ)

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

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

감사합니다.

강사 큰돌 올림.

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

tajan113님의 질문을 검토해보니, 수빈이와 동생이 만나야 하는 조건과 시간 설계에 관련된 문제로 보입니다. 수빈이의 최단 거리 탐색 및 동생의 시간 비교 알고리즘을 구현하셨다는 것은 올바른 방향이지만, 코드의 디버깅을 위해 주의해야 할 몇 가지 포인트가 있습니다.

1. 홀짝 시간 계산: 수빈이와 동생이 정확히 같은 시간에 같은 지점에 도달할 수 있는 조건은 둘의 도달 시간이 모두 홀수라든지 모두 짝수여야 한다는 것입니다. visited 배열을 사용해 수빈이의 최단 경로와 시간을 담고, 동생의 시간과 비교할 때 이 조건을 구현하는 것이 핵심입니다.

2. visited 배열 초기화: 2차원 배열을 사용하여 수빈이의 방문 상태와 동생의 시간을 비교하셨는데, 이때 배열의 초기화 상태와 업데이트 조건을 정확히 점검해 보세요. 배열 인덱싱 오류가 발생할 가능성이 있습니다.

3. 동생의 이동 경로 최적화: 동생이 이동할 수 있는 범위와 그것이 수빈이의 방문 상태와 비교하여 어떠한 영향을 미치는지를 코드로 명확히 검증해 보시기 바랍니다. 동생이 도달할 수 없는 경우도 있음을 고려해야 합니다.

이와 관련된 기존 질문들을 찾았으며, 유사한 문제 및 구조적 해결책에 대한 답변은 아래 링크에서 참고하실 수 있습니다.

• “3-I 질문있습니다.”: 수빈이와 동생의 시간과 장소 비교 조건을 다루며, 특히 홀수, 짝수 시간 개념을 활용한 해결책이 포함되어 있습니다.

• “3-I 17071번 숨바꼭질 5 질문있습니다.”: 코드 구현 시 시간 비교 로직과 관련하여 남녀간의 이해를 도와주는 설명이 담겨 있습니다.

각 링크의 설명을 통해 중요한 문제 해결 개념을 확인해보시길 바랍니다.

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