백준 17244번: 아맞다우산

문제 설명

• https://www.acmicpc.net/problem/17244
• S에서 시작, 모든 X를 방문한 뒤 E로 도달하는 최소횟수를 구하는 문제입니다.

접근법

• 2차원 배열의 최단방문횟수를 구해야 하기 때문에 BFS를 사용해야 합니다.
• X는 모두 다른 물건을 의미하기 때문에 다른 무언가로 취급하기 위해 X를 cnt숫자로 변환해 줬습니다.
  • X라고 두면 열쇠를 4개 챙겼는지 열쇠1,휴대폰1,지갑1,안경1을 챙겼는지 구분할 수 없습니다.
• 현재 내가 지닌 물건의 상태에 따라 방문배열이 달라야 합니다.
• 비트마스킹으로 방문확인 및 방문처리를 구현했습니다.
  now[2]: 지금까지의 방문상태, keyNum: 현재 방문하는 곳의 값
  • 방문확인: (now[2] & (1<<keyNum))
  • 방문처리: (now[2] | (1<<keyNum))
    • 방문처리를 now[2] + keyNum으로 해서 틀렸었습니다.
      now[2]+keyNum은 1번열쇠와 2번열쇠를 함께 가지고 있는 상황과 3번열쇠 하나만 가지고 있는 상태가 동일한 방문배열을 사용하게 됩니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	static int N,M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		char[][] board = new char[N][M];
		Queue<int[]> q = new LinkedList<int[]>();
		int cnt = 0;
		int[] exit = new int[2];
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				board[i][j] =  s.charAt(j);
				if(board[i][j] == 'X') {
					board[i][j] = Integer.toString(cnt++).charAt(0);
				}else if(board[i][j] == 'S') {
					board[i][j] = '.';
					q.add(new int[] {i,j,0});
				}else if(board[i][j] == 'E') {
					exit = new int[] {i,j};
				}
			}			
		}
		
		BFS(board,cnt,q,exit);
		
		
	}
	public static void BFS(char[][] board, int cnt, Queue<int[]> q, int[] exit) {
		boolean[][][] v = new boolean[N][M][(int)Math.pow(2, cnt)];
		int time = 0;
		while(!q.isEmpty()) {
			int size = q.size();
			while(--size>=0) {
				int[] now = q.poll();
				if(now[2] == ((int)Math.pow(2, cnt)-1) && now[0] == exit[0] && now[1] == exit[1]) {
					System.out.println(time);
					return;
				}
				for (int d = 0; d < 4; d++) {
					int nx = now[0]+dx[d];
					int ny = now[1]+dy[d];
					if(0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] != '#' && !v[nx][ny][now[2]]) {
						v[nx][ny][now[2]] = true;
						if(board[nx][ny] == '.' || board[nx][ny] =='E') {
							q.add(new int[] {nx,ny,now[2]});
						}else {
							int keyNum = board[nx][ny] - '0'; // 현재 물건의 번호
							if((now[2]&(1<<keyNum)) == 0){ // 현재 물건을 아직 안챙겼으면
								keyNum = (now[2] | (1<<keyNum)); // 물건을 챙김
								// v[nx][ny][keyNum] = true; //약간의 시간단축
								q.add(new int[] {nx,ny,keyNum});
							}else{ // 이미 물건을 챙긴 상태로 그 위치를 지나감
								q.add(new int[] {nx,ny,now[2]});
							}
							
						}
					}
				}
			}
			time++;
		}
		
		
	}
	
	
}

기타

같이 풀어보면 좋은 문제

• 백준 1600번: 말이 되고픈 원숭이 // 정답풀이
• 백준 1194번: 달이 차오른다, 가자. // 정답풀이