인프런 커뮤니티 질문&답변
작성한 질문수
동생이 도착한 시간 - 수빈이가 도착한 시간 이 짝수일 때
작성
·
155
0
http://boj.kr/c287b933ed0442d4ba02329f7601b61b
선생님, 안녕하세요.
동생의 위치를 미리 구해놓고,
수빈이가 그 위치에 갈 수 있는지를 구하는 식으로 했습니다.
bfs를 이용했고, bfs의 로직 안에 현재 수빈이가 동생보다 빨리 방문했을 때를 처리하는 로직을 넣었는데요.
강의에서 설명해주셨던 것처럼, +1 -1을 하면 제자리로 돌아올 수 있고, 이때 2초가 걸리기 때문에 시간차가 반드시 짝수여야만 수빈이가 동생을 찾을 수 있기 때문에,
동생이 오는 시간 - 현재 수빈이가 오는 데 걸린 시간 이 짝수 일때, 동생이 오는 시간을 최소값으로 넣는 로직을 넣었습니다.
그런데 답이 틀렸다고 나와서, 1)왜그런건지? 2)visited배열을 2차원으로 한거랑 무슨 차이가 있는지 궁금합니다.
답변 2
1
안녕하세요 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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
이렇게 사실은 수빈이가 11초에 들어갈 수 있는 경우도 있을 수 있지만,
위 코드에서는 visited에 더 작은수 하나(짝수 혹은 홀수)만 들어갈 수 있게 하고,
이때문에 모든 경우의 수를 검사하는 것이 아니게 된다.
(따라서 단순히 수빈이와 동생의 시간차가 짝수라는 조건만으로는 안된다. 모든 조건을 보는 게 아니기 때문에)
>> 네 맞습니다. 역시 똑똑하시네요 ㅎㅎ 해당 반례가 있습니다.
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다.
google_user님의 질문은 수빈이와 동생이 만나는 시점을 구하는 과정에서 동생이 오는 시간과 수빈이가 도착한 시간의 차이가 짝수일 때를 필터링하는 방식에 대한 궁금증을 포함하고 있습니다. 이 내용에 대해 답변을 드리기 위해 기존에 다루었던 비슷한 컨텍스트의 답변을 찾아보았습니다.
해당 질문과 직접 연결되는 구체적 내용을 포함한 공유 링크는 다음과 같습니다:
- 3-I 17071번 숨바꼭질 5 질문있습니다.
이 질문에서는 수빈이가 동생을 만날 수 있는 조건, 특히 홀수와 짝수 시간에 방문한 경우에 대해 설명되어 있는 부분이 있는데, 이는 google_user님의 질문과도 일부 관련이 있습니다. 일반적으로 BFS 알고리즘을 사용하여 문제를 풀 때, 수빈이와 동생이 서로를 만날 수 있는 조건으로 시간 차이가 짝수여야 한다는 점은 중요한 관찰입니다. visited 배열을 2차원으로 사용하는 이유는 홀수와 짝수 시간에 도착한 경우를 구분하여 처리하기 위함입니다.
지식공유자 큰돌님이 제시한 설명을 보면, 수빈이와 동생이 만날 수 있는 조건을 구현하는 방법에 대한 깊이 있는 분석이 포함되어 있습니다. 홀수와 짝수 시간의 방문을 따로 처리하는 이유는 특정 시간에 방문했더라도, 수빈이가 해당 위치로 다시 돌아오는 경우를 계속해서 확인하면서, 만날 수 있는 정확한 시점을 파악하기 위함입니다.
구체적으로, 방문 배열을 2차원으로 구성하는 것은 [방문 시간의 홀짝성] 및 [특정 위치에 도착한 시간]을 동시에 고려하기 위함인데요, 이는 문제 풀이의 키 포인트가 되는 부분입니다. 지식공유자의 답변에서는 이러한 개념을 아주 세분화하여 설명하고 있으멀로, 해당 링크를 참조하시는 것이 이해에 도움이 될 것 같습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만콱스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
답변 감사드립니다~!
제가 이해한대로 다시 정리해보자면,
3이라는 정점에 수빈이가 10초에도 도착할 수 있고, 11초에도 도착할 수 있다. (+1,-1,*2 왔다리갔다리 하면서)
그런데
이 코드는 next visited가 더 큰 수는 들어갈 수 없기 때문에,
10초만 들어가고 11초는 들어가지 못하기 때문에,
만약 동생이 13초(홀수)에 도착하는 경우를 잡을 수 없다.
이렇게 사실은 수빈이가 11초에 들어갈 수 있는 경우도 있을 수 있지만,
위 코드에서는 visited에 더 작은수 하나(짝수 혹은 홀수)만 들어갈 수 있게 하고,
이때문에 모든 경우의 수를 검사하는 것이 아니게 된다.
(따라서 단순히 수빈이와 동생의 시간차가 짝수라는 조건만으로는 안된다. 모든 조건을 보는 게 아니기 때문에)
정리한다고 했는데, 그렇게 깔끔하진 못하네요.
그래도 이런 맥락으로 이해했는데, 이게 맞을까요??
다시한번 친절한 답변 감사드립니다~!