[백준] G5 16954 움직이는 미로 탈출 (java)

www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

 

풀이

 

1) 방문 체크를 위한 boolean형 3차원 배열 isVisited[r][c][d]을 만든다. <- r (행), c (열), d (맵이 움직인 횟수)

2) bfs 탐색을 한다.

2-1) 탈출조건은 현재 좌표가 맨 오른쪽위 일 경우 1을 출력하고 리턴한다.

2-2) for문을 돌려 9방향 탐색을 한다.

2-3) 탐색시 거르는 경우는 4가지 이다.

• 이동할 좌표가 범위 밖으로 나갈경우
• 이동할 좌표가 벽일경우
• 이동할 좌표의 한칸 위가 벽일경우
• 이미 방문된 경우

3) 맵이 움직인 횟수가 8 이상이면 더이상 횟수를 늘리지 않는다

4) while문이 끝나면 0출력 후 리턴

 

주의사항

 

1) 가장 중요한 포인트 : 맵이 움직인 횟수를 처리하는것

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G5_16954_움직이는미로탈출 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static char map[][];
	static boolean isVisited[][][];
	static final int N = 8;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		map = new char[N][N];
		isVisited = new boolean[N][N][9];
		for(int r=0; r<N; r++) {
			String line = input.readLine();
			for(int c=0; c<N; c++) {
				map[r][c] = line.charAt(c);
			}	
		}
		bfs();
	}
	private static void bfs() {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(N-1, 0, 0));
		isVisited[N-1][0][0] = true;
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			int fr = front.r;
			int fc = front.c;
			int fd = front.down;
			if(fr == 0 && fc == N-1) {
				System.out.println(1);
				return;
			}
			
			for(int d=0; d<9; d++) {
				int nr = fr + dr[d];
				int nc = fc + dc[d];
				int nd = Math.min(fd+1, 8);
				if(!isIn(nr, nc)) continue;
				if(isIn(nr-fd, nc) && map[nr-fd][nc] == '#') continue;
				if(isIn(nr-fd-1, nc) && map[nr-fd-1][nc] == '#') continue;
				if(isVisited[nr][nc][nd]) continue;
				queue.offer(new Node(nr, nc, nd));
				isVisited[nr][nc][nd] = true;
			}
		}
		System.out.println(0);
		return;
	}
	static class Node{
		int r;
		int c;
		int down;
		public Node(int r, int c, int down) {
			super();
			this.r = r;
			this.c = c;
			this.down = down;
		}
	}
	
	static int dr[] = {-1,-1,-1,0,0,0,1,1,1}; // 9방향
	static int dc[] = {-1,0,1,-1,0,1,-1,0,1};
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<N && c<N);
	}

	
	static String src =
			"........\r\n" + 
			"........\r\n" + 
			"........\r\n" + 
			"........\r\n" + 
			"#.......\r\n" + 
			".#######\r\n" + 
			"#.......\r\n" + 
			"........";
}

 

 

후기

 

 이 문제도 하루종일 풀다가 못풀고 결국 솔루션을 보게되었다. 솔루션을 볼때마다 느끼는 거지만 역시 세상은 넓고 천재는 많다. 왜 나는 3차원 배열이 생각이 안날까.. 아직도 멀었나보다.

이 문제를 풀면서 배우게 된 점

• 방문체크를 위해 3차원 배열을 쓰는 노하우
• Math.min(fd+1, 8)과 같이 제약사항이 있을경우 처리하는 법