문제

BOJ 2206: 벽 부수고 이동하기 https://www.acmicpc.net/problem/1600

풀이

처음에 했던 잘못 된 풀이

import java.util.*;
import java.io.*;

public class Main {
	
	static int W, H, K;
	static int[][] map;
	static boolean[][] isVisited;
	static int[] dx = {0, 0, 1, -1, -1, -2, -2, -1, 1, 2, 2, 1};
	static int[] dy = {1, -1, 0, 0, -2, -1, 1, 2, 2, 1, -1, -2};

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		K = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		
		map = new int[H][W];
		isVisited = new boolean[H][W];
		for(int i=0; i<H; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<W; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) {
				}
			}
		}
		
		int ans = bfs(0, 0, K);
		System.out.println(ans);
	}
	
	static int bfs(int x, int y, int k) {
		Queue<Pos> que = new LinkedList<>();
		
		que.add(new Pos(x, y, 0));
		isVisited[x][y] = true;
		
		while(!que.isEmpty()) {
			Pos p = que.poll();
			int curX = p.x;
			int curY = p.y;
			
			if(curX == H-1 && curY == W-1) { // 목적지에 도착하면 종료한다.
				return map[curX][curY];
			}
				
			if(p.hCnt < k) { // 아직 말 점프 쓸 수 있으면
				for(int t=0; t<12; t++) { // 1칸 짜리와 말 점프를 둘 다 쓸 수 있다.
					int nx = curX + dx[t];
					int ny = curY + dy[t];
					
					if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue; // map 범위 벗어나면 진행 멈추고 반복문 돌아감.
					
					if(map[nx][ny] == 0 && !isVisited[nx][ny]) { // 통과할 수 있는 길이고 아직 방문하지 않았다면
						if(t >= 4) { // 말 점프를 사용하여 도착한 새로운 좌표라면 그 횟수를 1 증가시킨다.
							p.hCnt++;
						}
						que.add(new Pos(nx, ny, p.hCnt)); // Queue에 넣는다.
						isVisited[nx][ny] = true; // 방문 처리
						map[nx][ny] = map[curX][curY]++; // 새로 도착한 좌표에 이전 좌표+1 한 값을 넣어준다.
					}
					
				}
			} else { // 이미 말 점프 다 썼으면
				for(int t=0; t<4; t++) {
					int nx = curX + dx[t];
					int ny = curY + dy[t];
					
					if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue; // map 범위 벗어나면 진행 멈추고 반복문 돌아감.
					
					if(map[nx][ny] == 0 && !isVisited[nx][ny]) { // 통과할 수 있는 길이고 아직 방문하지 않았다면
						que.add(new Pos(nx, ny, p.hCnt)); // Queue에 넣는다.
						isVisited[nx][ny] = true; // 방문 처리
						map[nx][ny] = map[curX][curY]++; // 새로 도착한 좌표에 이전 좌표+1 한 값을 넣어준다.
					}
				}
			}
			
		}
		return -1;
	}
	
	static class Pos{
		int x, y;
		int hCnt;
		
		Pos(int x, int y, int hCnt){
			this.x = x;
			this.y = y;
			this.hCnt = hCnt;
		}
	}
	
}  

정답 풀이

• 말 이동 횟수의 제한과 말 이동 방법으로는 장애물을 뛰어넘을 수 있다는 조건을 생각하며 해결한다.
• visited[x][y][hCnt] 처럼 3차원 배열을 사용하여 말 이동 횟수를 포함한 방문횟수를 확인한다.

• BFS 탐색 시작
  1. 현재 위치(curX, curY)에서 원숭이 이동 방법으로 4 방향을 탐색한다. (nx, ny, p.hCnt)
  2. 말 이동 횟수(hCnt) 가 아직 남았다면?(K 보다 작다면?)
     • 현재 위치(curX, curY)에서 말 이동 방법으로 8가지 탐색하고 말 이동 횟수를 1 늘려준다. (nx, ny, p.hCnt + 1)
  3. 현재 위치가 목적지(W-1, H-1)이 되면 이동 횟수(p.mCnt)를 리턴하고 종료한다.
• 모두 탐색을 해도 이동 횟수(p.mCnt)가 리턴되지 않으면 -1을 리턴한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int W, H, K;
	static int[][] map;
	static boolean[][][] visited;
	static int[] dx = {0, 0, 1, -1}; // 한 칸씩 이동
	static int[] dy = {1, -1, 0, 0}; // 한 칸씩 이동
	static int[] hx = {-1, -2, -2, -1, 1, 2, 2, 1}; // 말 점프
	static int[] hy = {-2, -1, 1, 2, 2, 1, -1, -2}; // 말 점프

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		K = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		
		map = new int[H][W];
		visited = new boolean[H][W][K+1];
		for(int i=0; i<H; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<W; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) {
				}
			}
		}
		
		int ans = bfs(0, 0, K);
		
		System.out.println(ans);
	}
	
	static int bfs(int x, int y, int k) {
		Queue<Pos> que = new LinkedList<>();
		
		que.add(new Pos(x, y, 0, 0));
		visited[x][y][0] = true;
		
		while(!que.isEmpty()) {
			Pos p = que.poll();
			
			int curX = p.x;
			int curY = p.y;
			
			if(curX == H-1 && curY == W-1) { // 목적지에 도착하면 종료
				return p.mCnt;
			}
			// 원숭이처럼 한 칸 씩만 탐색
			for(int t=0; t<4; t++) {
				int nx = curX + dx[t];
				int ny = curY + dy[t];
				
				if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
				if(visited[nx][ny][p.hCnt]) continue;
				
				if(map[nx][ny] == 0) {
					visited[nx][ny][p.hCnt] = true;
					que.add(new Pos(nx, ny, p.hCnt, p.mCnt + 1));
				}
			}
			// 말 점프 횟수 남아 있으면 말 점프로 탐색
			if(p.hCnt < k) {
				for(int t=0; t<8; t++) {
					int nx = curX + hx[t];
					int ny = curY + hy[t];
					
					if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
					if(visited[nx][ny][p.hCnt + 1]) continue;
					
					if(map[nx][ny] == 0) {
						visited[nx][ny][p.hCnt + 1] = true;
						que.add(new Pos(nx, ny, p.hCnt + 1, p.mCnt + 1));
					}
				}
			}
			
			
		}
		
		return -1;
	}
	
	static class Pos{
		int x, y;
		int hCnt;//말 점프 횟수
		int mCnt;//움직인 횟수
		
		Pos(int x, int y, int hCnt, int mCnt){
			this.x = x;
			this.y = y;
			this.hCnt = hCnt;
			this.mCnt = mCnt;
		}
	}
	
}
  
  
  

정리

• 원숭이 이동과 말 점프를 나눠서 탐색한다.
• 말 점프 횟수 제한과 같은 조건이 있다면 3차원 배열을 사용하여 해결한다.