2636 치즈 질문드립니다

Question

안녕하세요 강사님! http://boj.kr/48ed2af9ae684e12962097f10e0b0412 강의를 보기 전 혼자 힘으로 문제를 풀어보려 애써봤더니 효율적이지 못한 코드로 풀게 되었더라구요. BFS와 DFS를 둘 다 사용하는 식으로 풀었는데 비효율적인 방법인 것은 알겠지만 로직이 틀린 것 같진 않은데 통과가 안돼서 왜 틀렸는지 궁금합니다. 저는 이런 순서로 접근했습니다. 0. 따로 시간 변수를 두지 않고 배열의 값을 변경시키는 식으로 풀이하기 위해 입력의 치즈(1) 값을 1이 아닌 -1로 기록한다. 1. 0,0 은 언제나 가장자리 공기층이므로 공기층을 찾기 위한 dfs 함수에 0,0 만 돌린다. 여기서 가장자리 공기층을 큐에 전부 푸시한다. 2.치즈를 녹이기 위해 bfs를 돌린다. 치즈를 만나면 배열에 현재값 +1을 기록하고 다시 큐에 푸시한다. 3.bfs가 끝나면 배열을 한번 쭉 돌면서 최대 시간을 찾고, 그 시간값을 가진 좌표를 카운트한다. 문제 내의 테스트케이스와 백준 질문게시판의 반례, 해당 강의에 강사님이 달아주신 다양한 반례를 넣어보았지만 전부 정답을 출력했는데, 실제로 제출시에는 20%에서 틀렸습니다가 뜹니다. 제 로직에 어느 부분에서 문제가 있는지 궁금합니다ㅠㅠ 또 당연한 질문인 것 같지만.. 그래프 문제를 풀 때 dfs나 bfs 둘 중 하나로만 푸는 것이 효율적이겠지요? 좋은 강의 늘 감사합니다!

큰돌 · Answer

안녕하세요 레페님 ㅎㅎ 시도는 좋았습니다. ㅎㅎ 또 당연한 질문인 것 같지만.. 그래프 문제를 풀 때 dfs나 bfs 둘 중 하나로만 푸는 것이 효율적이겠지요? >> 아니요. 둘 다 해야 하는 문제도 있습니다. 그러나 이 로직은 굳이 2개가 필요하지 않은 로직입니다. void dfs(int y, int x) { visited[y][x] = 1; for (int i = 0; i < 4; i++) { ny = y + dy[i]; nx = x + dx[i]; // 유효하지 않은 좌표거나 방문한 좌표면 continue if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[ny][nx]) continue; // 치즈에 닿으면 continue if (cheese[ny][nx] == -1) continue; // 공기에 닿으면 dfs if (cheese[ny][nx] == 0) { // BFS를 위한 큐에 push q.push({ ny, nx }); dfs(ny, nx); } } return; } dfs로 연이여서 탐색이 가능한데 굳이 q를 사용해야 하는지.. 불필요한 코드라고 보시면 됩니다. 또한 굳이 공기층부터 시작하는 이유가 있을까요? 공기부터 시작해서 가장자리의 치즈부터 시작해야 하는게 아닐까요? // 공기에 닿으면 dfs if (cheese[ny][nx] == 0) { // BFS를 위한 큐에 push q.push({ ny, nx }); 이미 dfs에서 q푸시를 했을 때 방문처리가 되어있는데 // BFS를 위한 큐에 push q.push({ ny, nx }); dfs(ny, nx); 중복해서 한 부분도 비효율적입니다. while (q.size()) { tie(y, x) = q.front(); q.pop(); // 방문 처리 visited[y][x] = 1; 이런 코드를 디버깅하는게 사실 제일 어렵습니다. 분명히 맞는데 왜 틀릴까 하는 것이죠.. 그 때는 코드에서 불필요한 부분이 있는지. 를 중심으로 탐색해야 합니다. 얼핏 봤을 때 레페님의 로직은 저도 괜찮다고 생각했지만.. 이런식으로 불필요한 부분이 있는지 탐색했고 아 이런 반례를 처리하지 못하겠구나 생각했습니다. 반례는 다음과 같습니다. 8 7 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 정답 : 2 2 레페님 코드 : 1 20 감사합니다.