[백준-16985] Maaaaaaaaaze
이 문제는 백준의 골드 3레벨 문제이다.
이 문제는 구현해야 할 게 많아서 혹시 어디선가 틀리면 디버깅하기가 너무 막막했는데,
다행히 한번에 맞았습니다가 나왔다ㅠㅠㅠㅠ 감격...
하여튼, 이 문제는 이런 방식으로 풀어냈다.
1. 층 정하기(Floor, 순열)
2. 각 층의 방향 정해주기(direction, 중복순열)
3. 층이랑 방향대로 map에 넣어주기.(change)
4. 시작점인(0,0,0)이 1이라면 들어가기. (bfs)
이 과정을 계속해서 반복하면 된다.
층은 총 5개이고, 각 층마다 4개의 방향을 가질 수 있으니 5!*4^5 개의 조합이 생긴다.
이 것들을 다 돌려주면 된다.
일단 Floor 함수에서는 boolean 배열과 int 배열을 이용해 5개의 판을 가지고 순열을 만들어준다.
만약 cnt가 5개가 되면, 하나의 세트가 완료되었다는 것이므로 각 층의 방향을 정해주기 위해 direction함수를 불러준다.
static void Floor(int cnt) {
if(cnt == 5) {
direction(0);//각 층의 방향 정해주기
return;
}
for(int i=0; i<5; i++) { //층 순서대로 나오게 해주는 함수
if(!check[i]) {
floor[cnt] = i;
check[i] = true;
Floor(cnt+1);
check[i] = false;
}
}
}dirction 함수에서는 int 배열을 이용해 중복 순열을 만들어주었다. 한 개의 판은 한 층에만 갈 수 있지만, 방향은 같아도 상관이 없기 때문이다. 방향의 세트가 완성되면, change 함수에 넣어서 map에 값을 넣어준다. 매 조합마다 초기화를 해주어야하는데, 초기화 함수를 새로 부르기 보다는 새로운 조합이 생길 때 마다 map 배열을 새로 할당 해 주었다.
그 후, 만들어진 map의 (0,0,0)이 들어갈 수 있는 곳이라면 bfs를 시작한다.
static void direction(int cnt){ //중복순열. 방향 골라주기
if(cnt == 5) {
map = new int[5][5][5]; //새로운 조합이 생길 때 마다 할당.
change();//층이랑 방향 설정.
if(map[0][0][0] == 1) //들어갈 수 있는 길이면 들어가기
bfs(); //bfs돌리기
return;
}
for(int i=0; i<4; i++) {
dir[cnt] = i;
direction(cnt+1);
}
}change 함수에서는 3중 포문을 돌며, map의 0층부터 쌓아나간다.
주석에 달아 놓았지만, dir이 0이면 그대로, 1이면 반시계 방향 90도, 2면 180도, 3이면 270도 회전한 모양이다.
층은 미리 계산해 두었던 floor[k] 배열을 이용해서 지정해주었다.
마지막 bfs!
사실 보통의 bfs와 크게 다르지 않기는 한데, 이번에는 3차원 배열을 돌 것이기 때문에 전후좌우상하 로 나누어서 계산해주었다. map[k][i][j] 에서 상하로 갈 때는 k값이 바뀌고, 전후좌우로 갈 때는 i,j 값이 바뀌기 때문에 델타 배열을 6개로 만들어서 계산해주었다.
static void bfs(){
boolean[][][] visited = new boolean[5][5][5];
Queue<Point> q = new LinkedList<>();
visited[0][0][0] = true;
q.add(new Point(0,0,0,0));
while(!q.isEmpty()) {
Point p = q.poll();
// System.out.println(p.k+" "+p.r+" "+p.c+" "+p.cnt);
if(p.k == 4 && p.r == 4 && p.c == 4) { //도착
if(p.cnt < ans)
ans = p.cnt;
return;
}
for(int i=0; i<6; i++){ //전,후,좌,우,상,하
if(i<4) { //전후좌우. 같은 층 안에서만 움직일 것
int nr = p.r + dr[i];
int nc = p.c + dc[i];
if(nr<0|| nc<0|| nr>=5 || nc>= 5)
continue;
if(visited[p.k][nr][nc])
continue;
if(map[p.k][nr][nc] == 1) {
visited[p.k][nr][nc] = true;
q.add(new Point(p.k, nr,nc,p.cnt+1));
}
}
else { //상하. 층 이동 함
int nk = p.k + dr[i];
if(nk<0 || nk>=5)
continue;
if(visited[nk][p.r][p.c])
continue;
if(map[nk][p.r][p.c] == 1) {
visited[nk][p.r][p.c] = true;
q.add(new Point(nk,p.r,p.c,p.cnt+1));
}
}
}
}
}
이제 전체코드이다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Maaaaaaaaaze_16985 { //백준 골드3
static int[][][] map;
static int[][][] copy;
static boolean[] check;
static int[] floor;
static int[] dir;
static int[] dr = {-1,1,0,0,-1,1};
static int[] dc = {0,0,-1,1,0,0};
static int ans = 987654321;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
copy = new int[5][5][5];
for(int k=0; k<5; k++) { //입력
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
copy[k][i][j] = sc.nextInt();
}
}
}
check = new boolean[5];
floor = new int[5];
dir = new int[5];
Floor(0);
ans = (ans == 987654321? -1:ans);
System.out.println(ans);
}
static void Floor(int cnt) {
if(cnt == 5) {
direction(0);//각 층의 방향 정해주기
return;
}
for(int i=0; i<5; i++) { //층 순서대로 나오게 해주는 함수
if(!check[i]) {
floor[cnt] = i;
check[i] = true;
Floor(cnt+1);
check[i] = false;
}
}
}
static void direction(int cnt){ //중복순열. 방향 골라주기
if(cnt == 5) {
map = new int[5][5][5]; //새로운 조합이 생길 때 마다 할당.
change();//층이랑 방향 설정.
if(map[0][0][0] == 1) //들어갈 수 있는 길이면 들어가기
bfs(); //bfs돌리기
return;
}
for(int i=0; i<4; i++) {
dir[cnt] = i;
direction(cnt+1);
}
}
static void change() {
for(int k=0; k<5; k++) { //층별, 방향별 값 설정
if(dir[k] == 0) { //원상태 그대로
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
map[k][i][j] = copy[floor[k]][i][j];
}
}
}
else if(dir[k] == 1) { //반시계방향 90도
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
map[k][i][j] = copy[floor[k]][j][4-i];
}
}
}
else if(dir[k] == 2) { //반시계방향 180도
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
map[k][i][j] = copy[floor[k]][4-i][4-j];
}
}
}
else if(dir[k] == 3){ //반시계방향270도
for(int i=0; i<5; i++) {
for(int j=0; j<5; j++) {
map[k][i][j] = copy[floor[k]][4-j][i];
}
}
}
}
}
static void bfs(){
boolean[][][] visited = new boolean[5][5][5];
Queue<Point> q = new LinkedList<>();
visited[0][0][0] = true;
q.add(new Point(0,0,0,0));
while(!q.isEmpty()) {
Point p = q.poll();
// System.out.println(p.k+" "+p.r+" "+p.c+" "+p.cnt);
if(p.k == 4 && p.r == 4 && p.c == 4) { //도착
if(p.cnt < ans)
ans = p.cnt;
return;
}
for(int i=0; i<6; i++){ //전,후,좌,우,상,하
if(i<4) { //전후좌우. 같은 층 안에서만 움직일 것
int nr = p.r + dr[i];
int nc = p.c + dc[i];
if(nr<0|| nc<0|| nr>=5 || nc>= 5)
continue;
if(visited[p.k][nr][nc])
continue;
if(map[p.k][nr][nc] == 1) {
visited[p.k][nr][nc] = true;
q.add(new Point(p.k, nr,nc,p.cnt+1));
}
}
else { //상하. 층 이동 함
int nk = p.k + dr[i];
if(nk<0 || nk>=5)
continue;
if(visited[nk][p.r][p.c])
continue;
if(map[nk][p.r][p.c] == 1) {
visited[nk][p.r][p.c] = true;
q.add(new Point(nk,p.r,p.c,p.cnt+1));
}
}
}
}
}
static class Point{
int k,r,c,cnt;
Point(int k, int r, int c, int cnt){
this.k = k;
this.r = r;
this.c = c;
this.cnt = cnt;
}
}
}
생각보다 빨리 잘 풀어내서 기분이 좋다:)
다른것도 이렇게 잘 풀리면 좋을텐데ㅠㅠ