[프로그래머스] 미로 탈출 🏃 (Java)

hoonssac·2025년 5월 12일

BFS Java algorithm coding test programmers

Coding test

목록 보기

3/9

문제 링크

📊 문제 파악

주이전 2차원 배열 maps는 캐릭터가 탐험하는 미로 지도를 나타냅니다.
각 문자는 다음과 같은 의미를 가집니다.

문자	의미
S	시작 지점
L	레버 위치 (필수 통과)
E	출구 (탈출 지점)
X	벽 (통과 불가)
O	빈 공간 (통과 가능)

🎯 목표

S에서 출발하여 반드시 L(레버)을 거쳐 E(출구)로 가야 함.
최단 거리를 구하고, 없다면 -1을 반환.

✏️ 접근 방법

지도 정보 파싱 및 좌표 저장

먼저 주어진 배열 maps를 2차원 문자 배열로 변환하고, 시작(S), 레버(L), 출구(E)의 좌표를 추출합니다.

이후 BFS 탐색의 출발점 및 도착점으로 사용할 좌표를 미리 확보하기 위함이죠!

for (int i = 0; i < rowSize; i++) {
    for (int j = 0; j < colSize; j++) {
            char tmp = maps[i].charAt(j);
            map[i][j] = tmp;

            switch(tmp) {
                case 'S': startR = i; startC = j; break;
                case 'L': leverR = i; leverC = j; break;
                case 'E': endR = i; endC = j; break;
            }
    }
}

BFS로 시작 → 레버 거리 계산

S에서 L로 가는 최단 거리를 구하기 위해 BFS를 수행합니다.
이떄 visited 배열을 사용해 중복 탐색을 방지합니다.
```
int firstDist = bfs(startR, startC, leverR, leverC);
```

BFS 구현

queue.add(new int[]{startR, startC, 0});  // 시작 좌표 및 거리

while (!queue.isEmpty()) {
    int[] cur = queue.poll();
    int r = cur[0], c = cur[1], dist = cur[2];
		visited[r][c] = true;
    if (r == endR && c == endC) return dist;  // 도착 시 종료

    for (int i = 0; i < 4; i++) {
        int newR = r + step[i][0];
        int newC = c + step[i][1];

        if (유효한 이동 조건) {
            queue.add(new int[]{newR, newC, dist + 1});
        }
    }
}

visited 초기화 후 레버 → 출구 거리 계산

visited 배열은 재사용되므로, 다음 탐색을 위해 초기화가 필요합니다.
만약, visited 배열이 이전 탐색 상태를 가지고 있으면, 다음 BFS가 의도대로 작동하지 않기 때문이죠!
```
visited = new boolean[rowSize][colSize];  // 새로 초기화
int secondDist = bfs(leverR, leverC, endR, endC);
```

경로 유효성 판단 및 결과 반환

시작 지점 → 레버, 레버 → 출구 중 하나라도 막히면 탈출 실패이기 때문에

해당 경우에는 -1을 반환하도록 예외 처리를 해줍니다.

if (firstDist == -1 || secondDist == -1) {
    return -1;  // 도달 불가능한 경우
} else {
    return firstDist + secondDist;  // 총 이동 거리 반환
}

🚨 문제 발생

그런데 어라..? 절반의 테스트 케이스에서 시간 초과 혹은 메모리 초과가 발생했습니다.

✨ 문제 해결

문제의 원인은 방문 처리 코드인 visited[r][c] = true; 의 위치가 잘못된 것이었습니다.

현재 로직은 큐에서 꺼낼 때 방문처리를 하고 있습니다.
그런데, 큐에서 꺼낼 때 방문처리를 하게 되면, 같은 칸이 큐에 여러 번 들어가는 현상이 발생하게 됩니다.

예를 들어 아래와 같은 상황이 있습니다.

S O
O O

S에서 오른쪽과 아래쪽을 모두 큐에 넣었습니다.

그런데 visited를 큐에서 꺼낼 때 처리하면, 오른쪽/아래쪽에서 또 그 인접 칸들을 큐에 넣을 수 있게 되어, 같은 칸이 큐에 여러 번 들어가게 됩니다.
결과적으로 불필요한 중복 탐색이 많아져 시간복잡도와 메모리 초과 가능성이 증가하게 되었던 것이죠!

if (!visited[newR][newC] && map[newR][newC] != 'X') {
    visited[newR][newC] = true; // ⭐ 바로 여기서 처리
    queue.add(new int[]{newR, newC, dist + 1});
}