백준 17244 : 아맞다우산

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

17244번: 아맞다우산

[ 문제풀이 ]

전형적인 bfs + 비트마스킹 문제로 챙긴 물건의 상태를 표현하여 중복방문을 체크해주면서 목적지까지 도달하면 되는 문제이다.

물건이 최대 5개이고 맵이 최대 50x50이기 때문에 비트마스킹을 모른다고 하여도 물건을 차례대로 선택하는 모든 경우의 수를 탐색해도 통과될 것 같긴 하다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Node {
		int y, x, state, time;

		public Node(int y, int x, int state, int time) {
			this.y = y;
			this.x = x;
			this.state = state;
			this.time = time;
		}
	}
	
	static int N, M, sy, sx, Xs, size;
	static char[][] map;
	static boolean[][][] visit;
	static Map<Integer, Integer> hm;
	
	static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
	
  	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			hm = new HashMap<>();
			map = new char[M][N];
			for (int i = 0; i < M; ++i) {
				String input = br.readLine();
				for (int j = 0; j < N; ++j) {
					map[i][j] = input.charAt(j);
					if (map[i][j] == 'S') {
						sy = i; sx = j;
					}
					if (map[i][j] == 'X') {
						hm.put(i * 10 + j, Xs++);
					}
				}
			}
			
			size = 1 << Xs;
			visit = new boolean[size][M][N];
			bw.write(bfs() + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
  	
  	public static int bfs() {
  		Queue<Node> q = new LinkedList<>();
  		q.offer(new Node(sy, sx, 0, 0));
  		visit[0][sy][sx] = true;
  		
  		while (!q.isEmpty()) {
  			Node n = q.poll();
  			
  			if (map[n.y][n.x] == 'E' && n.state == size - 1) {
  				return n.time;
  			}
  			
  			for (int d = 0; d < 4; ++d) {
  				int ny = n.y + dir[d][0];
  				int nx = n.x + dir[d][1];
  				
  				if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
  				if (map[ny][nx] == '#' || visit[n.state][ny][nx]) continue;
  				
  				visit[n.state][ny][nx] = true;
  				if (map[ny][nx] == 'X') {
  					int idx = hm.get(ny * 10 + nx);
  					q.offer(new Node(ny, nx, n.state | (1 << idx), n.time + 1));
  					continue;
  				}
  				q.offer(new Node(ny, nx, n.state, n.time + 1));
  			}
  		}
  		return -1;
  	}
}