2-Q 질문있습니다

Question

안녕하세요, 2-Q 문제 질문있습니다.
http://boj.kr/3ce7270b49e1494aa875c3b9a9f48e1c
제가 제출한 코드인데요, 매번 visited배열을 초기화하면 맨 바깥쪽 공기는 중복으로 탐사하는 부분이 싫어서

memset(visited,0,sizeof(visited));

을 없애고,

//녹이기
        for(auto k : meltCheese){
            questionMap[k.first][k.second]=0;
            visited[k.first][k.second]=0;
        }

이렇게 녹이는 부분만 다시 visited배열을 0 으로 만들고 탐색하면 답이 다르게 나오는데 이부분이 왜 그런지 잘 모르겠습니다..!!

큰돌 · Answer

안녕하세요 정현님 ㅎㅎ meltCount++; int firstY, firstX; tie(firstY, firstX) = meltCheese[0]; 로직 자체가 처음부터 dfs를 돌리는 것으로 되어있는데 방문처리를 녹은 치즈만 해버리게 되면 a -> b a -> b -> c ... 이렇게 탐색할 때 (a) -> (b) -> c a -> b -> (c) 이렇게 c라는 치즈를 녹여서 c부분을 방문처리 해제했는데 다시 a부터 시작한다고 했을 때 여기는 이미 방문처리가 되어있고 해당부문은 방문처리해제가 안되어있기 때문에 아예 탐색자체가 불가능할 것 같습니다.   다만, 이런 생각자체는 좋습니다. 좀 더 응용해서 dfs가 아닌 bfs로 드가시구 치즈를 녹이고 -> 해당 녹인 치즈를 queue에 담고 -> 해당 queue에 담은 것부터 다시 bfs를 시작하시면 더 좋은 코드가 될 것 같습니다.   또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.

인프런 AI 인턴 · Answer

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

이정현님이 치즈 문제를 해결하는 과정에서 visited 배열을 초기화하지 않으면서 meltCheese 부분만 초기화하려는 시도를 하셨군요. 자세히 설명드리겠습니다.

visited 배열을 초기화하는 이유는, 새롭게 탐색을 시작할 때 이전 탐색 정보가 영향을 미치지 않도록 하기 위함입니다. 만약 배열을 완전히 초기화하지 않고 특정 부분만 초기화했다면, 이전 단계에서 방문한 위치가 그대로 남아 있어 다음 탐색에 영향을 줄 수 있습니다. 이는 예상치 못한 오류를 유발할 수 있으며, 코드의 논리적 흐름을 방해합니다.

문제의 본질적인 이유는 다음과 같습니다:

혼재된 방문 기록: 만약 이전에 방문한 좌표들의 정보가 그대로 남아 있다면, 현재 탐색에서 필요없는 곳을 방문하지 않거나 잘못된 경로로 탐색하게 됩니다. 이는 결과적으로 최종 결과에 오류를 발생시킬 수 있습니다.
중복된 공기 탐사: 중복된 탐사를 피하기 위해 visited 배열을 건드렸지만, 초기화 과정에서 이러한 중복이 중요한 이유는 이를 통해 알고리즘의 정확성을 보장할 수 있기 때문입니다.

아래는 비슷한 질문을 다룬 게시물입니다. 해당 내용을 참조하여 문제 해결에 도움을 받으실 수 있습니다:

이 게시물들은 치즈 문제와 관련된 반례 및 해결법을 제공하며, 특히 중복 방문과 오류에 대한 예시를 다루고 있습니다.

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

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

2-Q 질문있습니다