문제 (1194번) 달이 차오른다, 가자
링크 : https://www.acmicpc.net/problem/1194
사용 언어 : JAVA
내 생각
초기 생각
- 옛날에 풀었던 아기상어와 비슷하게 풀면 되겠다고 생각했다.
- 근데 visited 배열을 어떻게 만들어야할지 당최.. 알 수가 없었다. (다른 문제를 풀어도 항상 여기서 막힌다..ㅎ)
그래서 위의 방법이 아닌가? 하면서 dfs로도 풀어보고 stack도 사용해보고 여튼 별 짓 다함
개선
- 비트 연산자를 활용해야 한다는 힌트를 듣고, visited 배열에 key 보유 상태를 나타내는 차원을 추가했다.
3차원 배열을 사용할 때마다 안터지나..? 하고 조마조마한데 생각보다 잘 안터지는 듯.
최종
bfs/dfs 문제는 푸는 방식이 거의 정해져 있다.
- bfs로 탐색. bfs 큐에 상태를 하나 꺼내서, 여기에서 나올 수 있는 다음 경우의 수를 탐색.
근데 만약 꺼낸 상태노드가 이전에 방문했었던 노드라면 탐색하지 않고 다음으로 스킵. - 방문 안한 노드라면 방문 표시를 해주고 현재 필드 값으로 추가적인 액션 취함.
- bfs 큐에 다음 상태를 삽입.
여기에 추가적으로 사용된 아이디어는 다음과 같다.
- 몇번의 depth 때 1에 도달하는지 계산하기 위해 bfs용 queue를 2개 사용
depth = i의 노드를 담은 Qcur에서 꺼낸 노드 Ncur가 있을 때, 그 Ncur에서 나아갈 수 있는 다음 노드들을 Qnext에 집어넣는다. 모든 Qcur의 노드에서 이런 과정을 거쳤다면, 결과적으로 Qnext에 담긴 모든 노드는 Qcur에 속한 노드들의 자식들을 모아놓은 큐가 된다. 따라서 두 큐 사이의 depth는 1의 차이가 난다. 이것을 활용해 최단 경로의 길이를 구할 수 있다.
- visited[row][col][key status]
key status가 왜 필요하냐? 바로 문제에 나온 '열쇠'와 '문'이라는 제약조건 때문이다.
bfs 탐색을 중단해야하는 경우는 왔던 방향을 제외한 삼방이 벽, (열 수 없는) 문으로 막히거나 맵 가장자리어서 움직일 수 없는 경우이다. 보통은 여기까지 오면 다른 쪽으로 갈 수 있는 방법이 없으니 쿨하게 중단하고 다음 탐색을 시작하면 되지만, 이 문제는 '문을 열면 진행되는 경우'가 있기 때문에 만약 내가 열쇠를 가지고 있다면 왔던 길을 되돌아가서 그 문을 열어봐야 한다는 것이다.
그러니까, 원래같으면 방문했던 길은 다음 탐색 후보에서 쳐내야 했는데 이제는 한번 방문했던 길을 다시 방문할 수도 있기 때문에 위치 정보만으로 탐색 후보에서 쳐낼 수 없는 상황이다. 때문에 '이 노드를 다시 탐색할 것인가?' 에 대한 새로운 기준이 하나 더 필요해졌다. 그리고 그 해결책이 key 보유 정보를 담는 것이다.
위의 경우에는 visited[2][1][0], visited[1][1][0]을 true로 만들면서 a로 이동한다. 그리고 a에 도달했을 때 새로운 key를 얻으면서 key 보유 상태값이 바뀐다. 그러면 이제부터 visited[위치][0]는 버려지고 새로운 visited[위치]['a']를 사용하게 된다! 그러면 map[0][0]에서 내려오는 것이 가능해진다. (visited[2][1]['a'], visited[1][1]['a']는 false이니까)
위처럼 key 보유 상태값에 변화가 없다면? 계속 visited[위치][0]를 참조할 것이므로 더이상 움직일 수 없어 탐색이 중단될 것이다.
- key 보유 상태를 나타내기 위한 비트연산자 사용
visited의 3번째 항목 크기를 {1<<(key 종류 개수)}만큼 만들어준다. 여기에 000000(2) 값으로 초기화해주고, 새로운 key를 주웠을 때 1<<(key-'a') 값을 더해준다.
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_BJ_1194_달이차오른다가자 {
// r,c : 노드의 위치, key: 노드의 key 보유 상태
static class Node {
int r, c;
int key;
public Node(int r, int c, int key) {
this.r = r;
this.c = c;
this.key = key;
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 미로의 높이
int M = Integer.parseInt(st.nextToken()); // 미로의 너비
char maze[][] = new char[N][M];
int start[] = new int[2]; // 시작 위치 (0)
for(int i=0; i<N; i++) {
String line = br.readLine();
maze[i] = br.readLine().toCharArray();
if(line.contains("0")) {
start[0] = i;
start[1] = line.indexOf('0');
}
}
System.out.println(findWayExit(maze, start));
}
// 차례로 상, 우, 하, 좌
static int dr[] = {-1, 0, 1, 0};
static int dc[] = {0, 1, 0 ,-1};
private static int findWayExit(char[][] maze, int[] start) {
int r = maze.length;
int c = maze[0].length;
/* visited
* [r][c]: 방문 위치
* [1<<6]: 키가 A, B, C, D, E, F 총 6가지 이므로 이 키들의 보유 여부를 나타낼 수 있는 비트가 필요하다.
* -> 6비트짜리 int를 담을 수 있는 크기로 만듦
*/
boolean[][][] visited = new boolean[r][c][1<<6];
// 현재 이동 가능한 노드를 담는 큐
Queue<Node> current = new LinkedList<>();
// 맨 처음 시작 위치(start[])와 처음 key 보유 상태(000000)를 담은 노드 객체를 넣어준다.
current.add(new Node(start[0], start[1], 0));
// bfs의 깊이를 나타냄
int dist = 0;
while(!current.isEmpty()) {
++dist;
// 현재 노드에서 이동할 수 있는 다음 상태를 담는 큐
Queue<Node> next = new LinkedList<>();
while(!current.isEmpty()) {
// 현재 큐에서 뽑아낸 상태
Node cur = current.poll();
// 현재 상태에서 사방으로 탐색
for(int m=0; m<4; m++) {
int nr = cur.r+dr[m];
int nc = cur.c+dc[m];
int nkey = cur.key;
// 다음 노드가 미로를 벗어나면 탐색 중단
if(0>nr || nr>=r || 0>nc || nc>=c) continue;
// 다음 노드의 필드 값
char pos = maze[nr][nc];
if(pos == '1') return dist; // 종료지점일 경우 bfs의 깊이를 리턴
if(pos == '#') continue; // 진행할 수 없는 벽일 경우 탐색 중단
if(visited[nr][nc][nkey]) continue; // 현재 상태에서 방문했던 노드일 경우 탐색 중단
visited[nr][nc][nkey] = true; // 방문 안했었다면 탐색. 먼저 방문 표시 해줌
// 현재 위치에 키가 있다면 무조건 줍는다.
if('a'<=pos && pos<='z') {
// 현재 노드가 가진 키 상태에 지금 얻은 키 정보를 넣고 다음 탐색 큐에 추가
nkey |= 1<<(pos-'a');
next.add(new Node(nr, nc, nkey));
}
// 현재 위치에 문이 있다면
else if('A'<=pos && pos<='Z') {
// 현재 노드가 그 문의 열쇠를 가진 경우에만 다음 탐색 큐에 추가
if((nkey & 1<<(pos-'a')) != 0){
next.add(new Node(nr, nc, nkey));
}
}
// 그 외 빈칸이나 시작점일 경우 다음 탐색 큐에 추가
else if(pos == '.' || pos == '0') {
next.add(new Node(nr, nc, nkey));
}
}
}
// 현재 이동할 수 있는 노드를 다 탐색했다면 다음 탐색할 노드를 current 큐에 담음
current = next;
}
// 탐색할 수 있는 모든 노드를 다 돌았음에도 중간에 1을 만나지 못했다면 -1 반환
return -1;
}
}느낀점
- visited를 어떻게 설정해야 하는지가 정말 어려운 것 같다.. 더...... 열심히 푸는 걸로.............
