b9328. 열쇠

 

https://www.acmicpc.net/problem/9328

 

 

 

🔑 자바로 푸는 열쇠 문제 풀이 (백준 9328)

 

 

📌 문제 개요

 

감옥의 평면도가 주어졌을 때, 상하좌우 이동을 통해 가능한 많은 문서(’$’)를 얻는 것이 목표입니다.

 

• 벽은 *, 빈 공간은 ., 문은 A~Z, 열쇠는 a~z, 문서는 $
• 열쇠가 있어야 문을 통과할 수 있음
• 열쇠는 한 번 획득하면 해당 종류의 문을 모두 열 수 있음
• 감옥의 외곽 어느 지점에서든 침입 가능

 

---

 

💡 예제 입력

1
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz

 

예제 출력

3

 

---

 

🧠 알고리즘 접근 방식

 

이 문제는 BFS(너비 우선 탐색) 을 기반으로 풀 수 있으며, 열쇠를 획득할 때마다 새롭게 열리는 문들을 다시 확인해야 하므로 추가적인 상태 관리가 필요합니다.

 

---

 

🔁 전체 코드 (BFS 기반)

// 코드 전체는 생략 없이 위 본문 참고
// 핵심 함수: check(), BFS(), main(), logic()

전체 코드는 위 질문 본문에 포함되어 있으며, 핵심 로직은 check() 함수입니다.

 

---

 

🧾 핵심 로직 설명

 

 

1. 시작점 처리: 외곽 탐색

for (int i = 0; i < width; i++) {
    check(0, i, hasKey, 0);
    check(height-1, i, hasKey, 0);
}
for (int i = 0; i < height; i++) {
    check(i, 0, hasKey, 0);
    check(i, width-1, hasKey, 0);
}

→ 외곽에서 진입 가능한 모든 점을 check()로 진입 시도

 

---

 

2. 열쇠를 먹으면 저장된 문들 개방

else if(map[x][y] >= 'a' && map[x][y] <= 'z'){
    hasKey[map[x][y]-'a'] = true;
    ...
    for (Node cur : savedDoor.get(map[x][y])) {
        q.add(cur);
        isVisited[cur.x][cur.y] = true;
    }
}

→ 열쇠 획득 시, savedDoor에 저장되어 있던 대응 문을 모두 큐에 재추가

 

---

 

3. 문을 만나면 열쇠 유무에 따라 처리

else if(map[x][y] >= 'A' && map[x][y] <= 'Z'){
    if(hasKey[map[x][y]-'A']) {
        map[x][y] = '.';
        isVisited[x][y] = true;
    } else {
        savedDoor.get(Character.toLowerCase(map[x][y])).add(new Node(x,y));
        return;
    }
}

→ 열쇠 없으면 저장만 해두고 나중에 다시 방문

 

---

 

❗️ 직접 겪은 실수 정리

 

 

1. '.' 칸에 isVisited = true 를 누락

else if(map[x][y] == '.'){
    isVisited[x][y] = true; // ✅ 반드시 방문 처리 필요!
}

→ 방문 처리 안 해줘서 같은 칸을 stack over flow 발생

 

---

 

2. 대문자 문에서 hasKey 잘못 조회

// ❌ 잘못된 버전
hasKey[map[x][y] - 'a'] // 대문자에 대해 'a' 기준 인덱싱하면 IndexOutOfBounds or null 발생

// ✅ 올바른 버전
hasKey[map[x][y] - 'A']

→ 열쇠 배열은 a~z 기준 26칸. 대문자에 대해선 반드시 'A'로 변환해야 함

 

---

 

✅ 핵심 포인트 정리

포인트	설명
외곽 진입	가장자리를 통해 BFS 시작
열쇠 획득 시 문 개방	HashMap<Character, List>로 문 저장
방문 체크	isVisited[][]는 ., 문서, 문 포함 모든 유효 칸에 필수
열쇠 인덱싱	항상 'a', 'A' 기준 인덱스 구분 철저히

 

---

 

🎯 결론: BFS + 상태 저장이 곧 열쇠다

 

이 문제는 단순한 탐색이 아니라, 상태 변화(열쇠 획득)에 따라 이동 가능성이 확장되는 문제입니다.

한 번 열쇠를 얻으면, 과거에 못 갔던 문을 돌아가야 한다는 점에서 상태 기반 BFS 설계가 중요합니다.

이미 방문했지만 열지못했던 문의 위치를 알파벳 기준으로 map에 정리하여 저장해놓고 열쇠 발견 시 

그 문의 위치를 queue에 넣어줌으로써 탐색을 돌아갈 수 있게 설계했던 방식이 정말 신의 한수 였던것 같습니다.