알고리즘/백준 문제 풀이
[BOJ] 1194번 : 달이 차오른다, 가자.
바켱서
2020. 7. 12. 03:13
https://www.acmicpc.net/problem/1194
접근 방법
처음 문제를 봤을 때 먼저 DFS, BFS 로 탐색을 해야한다는 것은 생각이 남
나는 BFS 탐색으로 했다.
가지고 있는 열쇠를 어떻게 표현해야 될 지에 대한 고민이 생김.
BitMask 사용 ( a 열쇠를 가지고 있음 → 1<<a || b 열쇠를 가지고 있음 → 1<<b)
문제 코드화
Vertex : 가지고 있는 열쇠 + 현재의 위치 (x, y)
-
코드 구현
class Location{ int x,y,bit; Location(int x,int y,int bit){ this.x = x; this.y = y; this.bit = bit; } }
Edge : 문에 대한 열쇠 Have || 빈 공간 ( . ) 에 대해 상하좌우
-
코드 구현
if(visit[nx][ny][bit] == 0){ // 그냥 빈 곳 이라면 if(map[nx][ny]=='.'){ visit[nx][ny][bit] = visit[x][y][bit]+1; map[nx][ny] = '.'; queue.add(new Location(nx,ny,bit)); } // 열쇠 or 문 else{ // 소문자 경우 if(map[nx][ny] >= 'a'){ // 몇번 째 키 add int newBit = bit|(1<<(map[nx][ny] - 'a')); visit[nx][ny][newBit] = visit[x][y][bit]+1; queue.add(new Location(nx,ny,newBit)); }else{ // 몇번 째 키 need int newBit = bit&(1<<(map[nx][ny] - 'A')); // 키가 존재 한다. if(newBit != 0){ visit[nx][ny][bit] = visit[x][y][bit]+1; queue.add(new Location(nx,ny,bit)); }// 없으면 그냥 아무 것도 안해 주면 됨. } } }
주의 할점
문제에서 잘 읽어보면 출구 ( 1 ) 이 한 개가 아니다.
Need Know
- BFS or DFS
- BitMask ( 몰라도 상관 없긴 하다. F면 100000 을 그냥 내가 직접 넣으면 되기 때문이지만.. 코드가 너무 지저분 할 것 같으니 알아두는게 좋다.)
전체 코드 ( Java )
import java.io.*;
import java.util.*;
class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N;
static int M;
static char[][] map;
static int[][][] visit;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static Queue<Location> queue;
public static void main(String[] args) throws NumberFormatException, IOException {
set();
bw.write(solve()+"");
bw.flush();
bw.close();
br.close();
}
static void set() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
queue = new LinkedList<>();
visit = new int[N][M][1<<5+1];
for(int i=0; i<N; i++){
String str = br.readLine();
for(int k=0; k<M; k++){
map[i][k] = str.charAt(k);
if(map[i][k]=='0') {
map[i][k] = '.';
queue.add(new Location(i,k,0));
}
}
}
}
static int solve(){
while(!queue.isEmpty()){
Location nowLoc = queue.poll();
int x = nowLoc.x, y = nowLoc.y, bit = nowLoc.bit;
// 수평&수직 이동
for(int i=0; i<4; i++){
int nx = x+dx[i], ny = y+dy[i];
if(nx>=N || ny>=M || nx<0 || ny<0 || map[nx][ny]=='#') continue;
// 출구에 도착할 경우
if(map[nx][ny]=='1'){
return visit[x][y][bit]+1;
}
if(visit[nx][ny][bit] == 0){
// 그냥 빈 곳 이라면
if(map[nx][ny]=='.'){
visit[nx][ny][bit] = visit[x][y][bit]+1;
map[nx][ny] = '.';
queue.add(new Location(nx,ny,bit));
}
// 열쇠 or 문
else{
// 소문자 경우
if(map[nx][ny] >= 'a'){
// 몇번 째 키 add
int newBit = bit|(1<<(map[nx][ny] - 'a'));
visit[nx][ny][newBit] = visit[x][y][bit]+1;
queue.add(new Location(nx,ny,newBit));
}else{
// 몇번 째 키 need
int newBit = bit&(1<<(map[nx][ny] - 'A'));
// 키가 존재 한다.
if(newBit != 0){
visit[nx][ny][bit] = visit[x][y][bit]+1;
queue.add(new Location(nx,ny,bit));
}// 없으면 그냥 아무 것도 안해 주면 됨.
}
}
}
}
}
return -1;
}
}
class Location{
int x,y,bit;
Location(int x,int y,int bit){
this.x = x;
this.y = y;
this.bit = bit;
}
}