위와 같은 입력이 들어왔다고 한다면, 아이템에게 번호를 부여하여 아래 그림과 같이 변경하였다.
아이템은 최대 5개이므로 char형 배열에 저장할 수 있다!
각 아이템 번호를 자릿수처럼 생각하며left shift 연산(`1<<n`)을 활용했다.
e.g. 아이템 2번 1을 왼쪽으로 2만큼 비트 이동한다. 100(bit) = 4(십진수)
경재가 여러 아이템을 발견한 경우 OR 비트연산(`|`)을 활용했다.
e.g. 경재가 0번 아이템만 가지고 있다가, 2번 아이템을 발견했을 때
경재가 최소 시간으로 물건을 찾고 외출해야하므로 너비 우선 탐색 BFS을 이용했다.
이때 방문처리는 현재 경재가 찾은 물건의 종류에 따라서 다르게 처리해야 한다고 생각했다.
아래 그림처럼 1번 아이템을 얻은 후 경재가 다시 왔던 길을 돌아가야하는 데, 방문처리를 2차원 배열로 한다면 돌아가지 못한다.
녹색이 경재의 현위치, 빨강색은 방문했던 곳
3차원 배열을 만들어 OR 비트연산한 결과에 따라서 다르게 방문처리할 수 있도록 구현했다.
OR 비트연산(`|`)을 통해 경재는 아이템이 하나도 없는 '0'부터 모든 아이템을 다 가진 '(1<<아이템 수) -1' 까지의 비트를 활용했다.
마지막으로 'E'에 도착했을 때, 경재가 모든 아이템을 다 찾았는지 체크하는 것은 비트 수를 확인했다.
1. 집의 구조를 입력받는다. 1. 해당 칸에 아이템이 있는 경우 'X', X대신 아이템 번호(`itemCount`)로 저장하고 `itemCount`를 증가시킨다. 2. 해당 칸이 출발 점인 경우, 변수로 위치를 저장하고 해당칸은 비어있는 곳 '.'으로 변경한다. 2. `findItem()`함수를 호출하여 외출하기까지 최소 시간을 구한다. 3. 경재의 움직임을 저장할 큐 `queue`를 선언한다. queue의 원소에는 {현재 위치의 행, 현재 위치의 열, 소요시간, 비트화한 획득한아이템}을 저장한다. 4. 방문처리할 3차원 boolean 배열 `visited`를 선언한다. [행][열][비트화한 획득한아이템] 5. 경재의 시작 위치에 맞게 `queue`에 원소를 넣고, `visited`방문처리를 한다. 경재는 아직 가진 아이템이 없으므로 비트화한 획득한아이템은 0이다. 6. `queue`가 빌 때까지 반복한다. 1. `queue`에서 원소를 빼 `node`에 저장한다. 2. 상하좌우 사방탐색을 하며 경재를 이동시킨다. 1. 이동한 위치가 벽'#'이거나, 방문한적이 있는 경우 다음 반복문으로 넘어간다. 2. 이동한 위치가 비어있는 곳'.'이라면, 이동한 위치에 방문 처리를 하고 `queue`에 원소를 넣는다. 3. 이동한 위치가 나가는 문'E'이고 경재가 모든 아이템을 다 챙겼다면 소요시간+1을 반환하며 함수를 종료한다. 4. 이동한 위치가 아이템이 있는 경우('0'~'4' 중 하나), OR 비트연산을 통해 아이템을 획득하고 이동한 위치에 방문 처리를 하고 `queue`에 원소를 넣는다. 7. `findItem()`함수가 종료됐다면, 반환값을 출력한다.
💻 전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N, M;
static int itemCount, s_i, s_j;
static char[][] map;
public static void main(String[] args) throws Exception {
init();
System.out.println(findItem());
}
static void init() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
N = Integer.parseInt(input.substring(0, input.indexOf(' ')));
M = Integer.parseInt(input.substring(input.indexOf(' ') + 1));
itemCount = 0;
map = new char[M][];
for (int m = 0; m < M; m++) {
map[m] = br.readLine().toCharArray();
for (int n = 0; n < N; n++) {
if (map[m][n] == 'X') {
map[m][n] = (char) (itemCount++ + '0');
} else if (map[m][n] == 'S') {
s_i = m;
s_j = n;
map[m][n] = '.';
}
}
}
}
static int findItem() {
final int[] di = new int[]{-1, 0, 1, 0};
final int[] dj = new int[]{0, 1, 0, -1};
Queue<int[]> queue = new LinkedList<>();
boolean[][][] visited = new boolean[M][N][1 << itemCount];
queue.offer(new int[]{s_i, s_j, 0, 0});
visited[s_i][s_j][0] = true;
while (!queue.isEmpty()) {
int[] node = queue.poll();
for (int z = 0; z < 4; z++) {
int ni = node[0] + di[z];
int nj = node[1] + dj[z];
if (map[ni][nj] == '#' || visited[ni][nj][node[3]]) continue;
if (map[ni][nj] == '.') {
visited[ni][nj][node[3]] = true;
queue.offer(new int[]{ni, nj, node[2] + 1, node[3]});
} else if (map[ni][nj] == 'E') {
if (itemCount == Integer.bitCount(node[3])) return node[2] + 1;
} else {
visited[ni][nj][node[3] | 1 << (map[ni][nj] - '0')] = true;
queue.offer(new int[]{ni, nj, node[2] + 1, node[3] | 1 << (map[ni][nj] - '0')});
}
}
}
return 0;
}
}
💫 리뷰
다른 방식으로 접근하고 있다가 비슷한 문제를 풀었던 기억이 나면서 해결할 수 있었던 문제!
