[백준 17244] 아맞다우산 (Java)

문제 링크: https://www.acmicpc.net/problem/17244

17244번: 아맞다우산

1. 주의할 점

- 특정 지점에 방문했을 때, 서로 다른 물건의 조합을 가지고 접근한 경우 어떻게 처리할 것인지 생각한다

 

2. 구현

- 위의 주의할 점의 예시로, (1,1)을 방문할 때 [0,1]번 물건을 가지고 접근했을 때와 [1,2]번 물건을 가지고 접근했을 때를 구분하기 위해 비트마스크를 이용한다(비트마스크 접근을 위한 추가 힌트: 최대 5개의 물건)

- 집의 구조를 Int방식으로 받고, -1: 이동할 수 있는 루트, 0~4: 물건, 5: 벽으로 바꾼 후, BFS 탐색을 수행한다

- Check[y][x][key] 배열을 전부 Maxi로 초기화 하고 시작하며, Check 배열은 (y,x)에 key만큼의 물건을 가지고 있을때 도착한 최단거리를 저장한다

- BFS()를 수행하여 모든 물건을 챙기고 목표지점에 도달했을 때, 종료한다(시간단축 위해 구현했으나 없어도 AC를 받을거라고 생각합니다)

 

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

class Main {
    static class Info{
        int y,x,val,knum;
        public Info(int y, int x, int val, int knum){
            this.y=y;
            this.x=x;
            this.val=val;
            this.knum=knum;
        }
    };
    
    static final int maxi = 5000;
    static final int dx[] = {0,1,0,-1};
    static final int dy[] = {-1,0,1,0};
    static int arr[][],check[][][];
    static int row,col,keys,sy,sx,ey,ex;
    
    static void bfs(){
        Info ii;
        Queue<Info> q = new LinkedList<>();
        q.offer(new Info(sy,sx,0,0));
        check[sy][sx][0]=0;
        
        while(!q.isEmpty()){
            ii = q.poll();
            int cx = ii.x;
            int cy = ii.y;
            int cv = ii.val;
            int ck = ii.knum;
            if(cx==ex && cy==ey && ck==((1<<keys)-1)) break;
            for(int i=0;i<4;i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if(nx>=0 && ny>=0 && nx<col && ny<row && arr[ny][nx]!=5){
                    int nk = ck;
                    int na = arr[ny][nx];
                    if(0<=na && na<keys) nk|=(1<<na);
                    if(check[ny][nx][nk]>cv+1){
                        check[ny][nx][nk]=cv+1;
                        q.offer(new Info(ny,nx,cv+1,nk));
                    }
                }
            }
        }
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    col = Integer.parseInt(st.nextToken());
	    row = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    keys=0;
	    arr = new int[row][col];
	    check = new int[row][col][32];
	    for(int i=0;i<row;i++)
	        for(int j=0;j<col;j++)
	            for(int k=0;k<32;k++)
	                check[i][j][k]=maxi;
	    
	    for(int i=0;i<row;i++){
	        str = br.readLine();
	        for(int j=0;j<col;j++){
	            char c = str.charAt(j);
	            if(c=='#') arr[i][j]=5;
	            else if(c=='S'){
	                sy = i;
	                sx = j;
	                arr[i][j]=-1;
	            }
	            else if(c=='E'){
	                ey = i;
	                ex = j;
	                arr[i][j]=-1;
	            }
	            else if(c=='.') arr[i][j]=-1;
	            else   arr[i][j]=keys++;    //열쇠
	        }
	    }
	    bfs();
		System.out.print(check[ey][ex][(1<<keys)-1]);
	}
}