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

안녕하세요. 선생님 ㅎㅎ 수업 잘 듣고 있습니다.

수업에서 알려주신 visited 배열의 값들을 증가시키면서 depth를 세는 방법 말고, 구조체를 정의해서 문제를 풀어봤는데요?

이게 어떤 방법은 틀리고 어떤 방법은 맞아서.. 어디서 차이가 나는지 궁금해서 질문드립니다.

<맞은 코드>
http://boj.kr/646d439f862e419ab3a865fdd7b1551b
일단 큐에 현재 노드에서 갈 수 있는 노드(4방향)를 모두 넣고, 이후에 조건으로 노드를 선별하고, 혹시나 해서 아래와 같은 탈출 조건을 추가했습니다.

        if (row == m - 1 && col == n - 1) {
            res = depth;
            break;
        }

<틀린 코드>

http://boj.kr/516fe108a71c492e8c1967455f7222a1
이번에는 큐에 넣기 전 예상되는 노드를 조건문을 통해서 선별하고 큐에 넣습니다.
제 생각에는 이 코드가 큐에 들어가는 노드의 개수가 적어서 속도가 빠를 것 같은데, 메모리 초과가 나오더라구요;;

<수정 코드>
http://boj.kr/f72b373b45464778b8313fec9713ba18
수정을 해봤는데 이번에는 틀린 코드랑 나머지는 똑같은데 반복문 안에서 큐에 넣자마자 바로 방문처리를 해주는 것입니다.

for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                continue;
            }
            if (puzzle[nc][nr] == 0) {
                continue;
            }
            if (visited[nc][nr]) {
                continue;
            }
            q.push({nr, nc, depth + 1});
            visited[nc][nr] = true;
        } 

이렇게 수정하니까 또 맞더라구요..
<수정 코드>가 <틀린 코드>보다 메모리를 덜 차지하는 것은 알겠는데, <맞은 코드>가 <틀린 코드>보다 메모리를 덜 차지하는 잘 모르겠어서 질문드립니다.

질문이 길어서 sorry...