동생이 도착한 시간 - 수빈이가 도착한 시간 이 짝수일 때

안녕하세요 google님 ㅎㅎ

좋은 아이디어네요.

이 아이디어의 경우 1. 동생의 거리를 먼저 구하는 로직 2. 최솟값을 구했음에도 불구, 계속해서 찾아야하기 때문에 이부분에 대한 시간이 걸리는 것. 이 2가지가 좀 걸리긴 하는데요.

어느정도 로직은 괜찮습니다.

6 0

이 테스트케이스의 경우 답 4를 올바르게 도출하지만 일부 컴파일러에서는 Segmentation fault가 뜹니다.

https://www.programiz.com/cpp-programming/online-compiler/

    while (q.size())
    {
        int cur = q.front();     // 수빈이의 위치
        int curD = visited[cur]; 

이부분에 cur을 디버깅해보시면 굉장히 많은 값이 출력 (cout << cur 해보시면)이 되는 것을 볼 수 있습니다.

이는 이 코드가 비효율적이라는 것을 의미합니다.

또한,

똑같은 지점에 수빈이는 홀수로 방문할 수 있고 짝수로 방문할 수 있는데 해당부분에 대한 로직은 없는 것 같습니다. 이 때문에 2차원으로 구축하셔야 합니다.

            if (next >= 0 && next <= 500000 && (visited[next] == -1 || visited[next] > curD + 1))
            // if (next >= 0 && next <= 500000 && curD + 1 <= 500000)
            {
                q.push(next);
                visited[next] = curD + 1;
            }

 이 로직만으로는 해당부분을 처리할 수 없습니다.

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

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

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

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

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

[홀수]에 방문

[짝수]에 방문.

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

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

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

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

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

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

감사합니다.

강사 큰돌 올림.

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

google_user님의 질문은 수빈이와 동생이 만나는 시점을 구하는 과정에서 동생이 오는 시간과 수빈이가 도착한 시간의 차이가 짝수일 때를 필터링하는 방식에 대한 궁금증을 포함하고 있습니다. 이 내용에 대해 답변을 드리기 위해 기존에 다루었던 비슷한 컨텍스트의 답변을 찾아보았습니다.

해당 질문과 직접 연결되는 구체적 내용을 포함한 공유 링크는 다음과 같습니다:
- 3-I 17071번 숨바꼭질 5 질문있습니다.

이 질문에서는 수빈이가 동생을 만날 수 있는 조건, 특히 홀수와 짝수 시간에 방문한 경우에 대해 설명되어 있는 부분이 있는데, 이는 google_user님의 질문과도 일부 관련이 있습니다. 일반적으로 BFS 알고리즘을 사용하여 문제를 풀 때, 수빈이와 동생이 서로를 만날 수 있는 조건으로 시간 차이가 짝수여야 한다는 점은 중요한 관찰입니다. visited 배열을 2차원으로 사용하는 이유는 홀수와 짝수 시간에 도착한 경우를 구분하여 처리하기 위함입니다.

지식공유자 큰돌님이 제시한 설명을 보면, 수빈이와 동생이 만날 수 있는 조건을 구현하는 방법에 대한 깊이 있는 분석이 포함되어 있습니다. 홀수와 짝수 시간의 방문을 따로 처리하는 이유는 특정 시간에 방문했더라도, 수빈이가 해당 위치로 다시 돌아오는 경우를 계속해서 확인하면서, 만날 수 있는 정확한 시점을 파악하기 위함입니다.

구체적으로, 방문 배열을 2차원으로 구성하는 것은 [방문 시간의 홀짝성] 및 [특정 위치에 도착한 시간]을 동시에 고려하기 위함인데요, 이는 문제 풀이의 키 포인트가 되는 부분입니다. 지식공유자의 답변에서는 이러한 개념을 아주 세분화하여 설명하고 있으멀로, 해당 링크를 참조하시는 것이 이해에 도움이 될 것 같습니다.

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