[백준]1194 달이 차오른다, 가자. (자바)
문제
지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.
- 빈 칸: 언제나 이동할 수 있다. ('.')
- 벽: 절대 이동할 수 없다. ('#')
- 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
- 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
- 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
- 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')
달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.
출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
입출력 예
풀이
방문 여부 체크가 핵심
각 지점(x,y)에서 가지고 있는 열쇠를 boolean 배열(key)로 표현
key[]를 2진수로 보고 방문 여부 3차원 배열 visited[x][y][key배열 10진수]로 방문 여부를 체크
이렇게 해서 같은 x,y좌표라도 현재 가지고 있는 열쇠의 종류에 따라 다른 지점으로 보도록 하였다.
코드
import java.io.*;
import java.util.*;
//백준 1194 달이 차오른다, 가자 -> bfs
public class Main {
static class Point{
int x,y,cnt;
boolean[] keys;
Point(int x,int y,int cnt, boolean[] keys){
this.x=x;
this.y=y;
this.cnt=cnt;
this.keys=keys;
}
}
static int n,m;
static char map[][];
static int[]dx= {1,-1,0,0};
static int[]dy= {0,0,1,-1};
static int covert(boolean[]c) {
int result=0;
for(int i=0;i<6;i++) {
if(c[i])
result+=(int)Math.pow(2, i);
}
return result;
}
static int bfs(int x,int y) {
Queue<Point>q=new LinkedList<>();
Point p = new Point(x,y,0,new boolean[6]);
q.offer(p);
boolean[][][]visited=new boolean[n][m][64];
visited[x][y][0]=true;
int cnt;
boolean[] key;
while(!q.isEmpty()) {
p=q.poll();
x=p.x;
y=p.y;
cnt=p.cnt;
key=p.keys;
if(map[x][y]=='1')return cnt;
for(int i=0;i<4;i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<m&&map[nx][ny]!='#'&&!visited[nx][ny][covert(key)]) {
boolean temp[]=new boolean[6];
System.arraycopy(key, 0, temp, 0, 6);
if(map[nx][ny]>='a'&&map[nx][ny]<='f') {
temp[(int)map[nx][ny]-97]=true;
q.add(new Point(nx,ny,cnt+1,temp));
}
else if(map[nx][ny]>='A'&&map[nx][ny]<='F') {
if(key[(int)map[nx][ny]-65]) {
q.add(new Point(nx,ny,cnt+1,temp));
}
}
else{
q.add(new Point(nx,ny,cnt+1,temp));
}
visited[nx][ny][covert(temp)]=true;
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
int[]curP= {0,0};
map=new char[n][m];
for(int i=0;i<n;i++) {
char[]temp=br.readLine().toCharArray();
for(int j=0;j<m;j++) {
map[i][j]=temp[j];
if(map[i][j]=='0') {
curP[0]=i;
curP[1]=j;
}
}
}
System.out.println(bfs(curP[0],curP[1]));
}
}
Author And Source
이 문제에 관하여([백준]1194 달이 차오른다, 가자. (자바)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jihun333/백준1194-달이-차오른다-가자.-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)