[백준] G5 1600 말이 되고픈 원숭이 (java)

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

풀이

 

1) 맵을 담을 배열 map과 방문체크를 할 배열 isVisited을 만든다.

1-1) isVisited는 boolean형 3차원 배열이며 r(행), c(열), k(말처럼 이동한 횟수)이다.  문제에서 k는 30까지밖에 못한다

2) Node 라는 class를 만든다. Node의 멤버는 r(행), c(열), k(말처럼 이동한 횟수), depth(총 이동 횟수) 이다.

3) 좌표(0,0)에서 bfs를 돌린다.

3-1) 먼저 큐를 생성 후 (0,0,0,0)을 담는다.

3-2) 큐가 비어있지 않다면 queue.poll로 맨앞의 Node(front)를 뽑는다

3-3) 만약 front의 좌표가 맵의 맨 오른쪽 아래에 도달할 경우 이동거리 depth를 출력후 리턴한다. 너비우선 탐색이므로 가장 처음에 나온 값이 최솟값이 된다.

3-4) 이제 범위, 장애물, 방문체크를 통해 다음 Node를 정하고 방문체크를 먼저한 뒤 조건에 맞는 Node를 queue에 넣는다. 

4) while문이 끝날때까지 3-3 조건을 만족 못할 경우, 시작점에서 도착점까지 갈 수 없는 경우 이므로 -1을 출력한다.

 

주의사항

 

1) for문 2개를 돌아야하므로 조건에 맞는 놈만 큐에넣는것이 아니라 큐에 넣은놈이 조건에 맞는지 확인해야한다.

2) 사방탐색은 언제나 해야하는것이고 말이동은 특정조건에서만 해야한다.

 

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_1600_말이되고픈원숭이 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int K,W,H,map[][];
	static boolean isVisited[][][]; // r, c, 말 이동유무
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		K = Integer.parseInt(input.readLine());
		tokens = new StringTokenizer(input.readLine());
		W = Integer.parseInt(tokens.nextToken());
		H = Integer.parseInt(tokens.nextToken());
		map = new int[H][W];
		isVisited = new boolean[H][W][31];
		for(int r=0; r<H; r++){
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<W; c++){
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}	
		}
		bfs(0,0);
	}
	

	private static void bfs(int r, int c) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(r, c, 0, 0));
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			int fr = front.r;
			int fc = front.c;
			int fk = front.k;
			if(fr == H-1 && fc == W-1) {
				System.out.println(front.depth);
				return;
			}
			if(!isIn(fr, fc) || map[fr][fc] == 1) continue;
			if(isVisited[fr][fc][fk]) continue;
			// 조건에 맞는 놈만 큐에넣는것이 아니라 큐에 넣은놈이 조건에 맞는지 확인할 수 있다.
			isVisited[fr][fc][fk] = true;
			for(int d=0; d<4; d++) {
				int nr = fr + dr[d];
				int nc = fc + dc[d];
				queue.offer(new Node(nr, nc, fk, front.depth+1));
			}
			if (front.k == K) continue;
			for(int d=0; d<8; d++) {
				int nr = fr + kr[d];
				int nc = fc + kc[d];
				queue.offer(new Node(nr, nc, fk+1, front.depth+1));
			}
		}
		System.out.println(-1);
	}


	static class Node{
		int r;
		int c;
		int k;
		int depth;
		public Node(int r, int c, int k, int depth) {
			super();
			this.r = r;
			this.c = c;
			this.k = k;
			this.depth = depth;
		}
	}
	
	static int dr[] = {0,0,-1,1};
	static int dc[] = {-1,1,0,0};
	static int kr[] = {-2,-2,-1,-1,1,1,2,2};
	static int kc[] = {-1,1,-2,2,-2,2,-1,1};
	
	
	static boolean isIn(int r, int c) {
		return (r>=0 && c>=0 && r<H && c<W);
	}
	

	static String src =
			"1\r\n" + 
			"4 4\r\n" + 
			"0 0 0 0\r\n" + 
			"1 0 0 0\r\n" + 
			"0 0 1 0\r\n" + 
			"0 1 0 0";
}

 

 

후기

 

이 문제를 처음에 dfs로 백트래킹을 이용하여 풀었고 테스트케이스, 반례모음집을 다 통과했다. 하지만 시간초과가 나온다. 너무 빡쳤다. 왜 원숭이가 말이 되고 싶었던 걸까..

보아하니 맵도 200 * 200 이었고 K는 30가지, 방향은 12방향 이라서 그랬나보다. 맵이 조금 작았으면 괜찮았을까..

결국 솔루션을 보았고 3차원 배열을 이용하여 방문체크를 해야한다는 사실을 깨달았다. 역시 세상엔 천재가 많다.

이 문제를 통해 내가 얻은 내용은

1) bfs와 dfs를 고를때 조건을 먼저 파악하여 상황에 맞는 것을 써야한다는 점.

2) 3차원 배열을 통해 방문체크를 좀더 효율적으로 할 수 있다는 점.

3) 조건이 2개이상 일때 (사방탐색 말이동 탐색 같이 for문을 2번 거쳐야하는 경우) 조건 체크를 따로 하지 않고 동시에 하는 쉬운 방법이 있다는것을 깨달았다.

4) 4스날