[구름] 초급 마법사의 시험 - bfs

리뷰

소요시간: 55분

오래걸린이유:

1. 문제를 잘못 파악함

다음칸이 벽인 경우 다음 칸으로 이동하는 것이 아니라, 현재방향 기준 다다음 칸으로 이동하도록 구현해야함.

 

2. 잘못구현으로 인한 디버깅

3차원배열로 visited 체크를 해야하는데, 위 1번의 이유로 2차원배열로 visited 체크를 진행하였음.

(로직에 따라 2차원배열도 가능할 것으로 보임)

 

※ 어떤 상태에서 최단거리로 방문하는지 고민할 것

※ 이 후의 탐색에 영향을 미치는 상태가 무엇인지 고민할 것

 

---

제한

1. 세로길이R, 가로길이 C: 1~100 → O(R^4)

 

 

유형

Goal: (1, 1)  →  (R, C) 최소시간 구하기

이동시간이 모두 동일하게 1이고, 최소시간을 구하는 문제이므로 0-1BFS

 

 

BFS 설계

• BFS는 방문한 당시의 "상태"를 고려해야 함.
  (∵ 상태에 따라, 이 후의 탐색가능 여부가 달라질 수 있기 때문)
• 시간복잡도: O ( R * C * 상태개수)
• 상태를 선별하는 기준은 다음 이동에 영향을 끼치는 상태가 무엇인지 고민할 것
  나무를 제거하기 위해 "현재 마력의 양"이 10만큼 필요함. 즉, "현재 마력의 양"은 이 후의 탐색에 영향을 끼치는 요인임.
• 예를들어, (row, col)을 방문했을 때 "현재 마력의 양"이 0이라면, 이 후의 탐색에서 나무를 지날 수 없을 것임. 하지만, 다른 최단거리로 (row, col)을 방문했을 때 "현재 마력의 양"이 10이라면, 이 후의 탐색에서 나무를 지날 수 있음.
• 즉, boolean[row][col][현재마력의 양] 으로 방문체크를 해줘야 함.
• 어떤 상태로 방문하는지 고민하고, 이 후의 탐색에 영향을 미치는 상태가 무엇인지 고민할 것!

 

1. bfs 초기 설정

시작지점: (1, 1)

현재비용: 0

현재마력의 양: 초기 마력의 양

private static void bfsStartSetting(Queue<int[]> q, boolean[][][] v) {
	q.add(new int[] {0, 0, wis, 0});	// (r, c, reminWis, cost)
	v[0][0][wis] = true;
}

 

2. 목적지: row == R-1 && col == C - 1

 

3. 연결된 곳: 인접 4방향

 

4. 갈 수 있는 곳

1) 중복방문 → 불가

현재 마력의 양으로 (row, col)을 이전에 방문했다면, 이 후의 방문은 불필요할 것임.

하지만, 다른 마력의 양으로 (row, col)을 방문했다면, 이는 방문을 해줘야할 것임.

(마력의 양에 따라 이 후의 탐색 가능 여부가 달라지기 때문)

if(visited[nr][nc][curWis]) {
	continue;
}

2) 다음칸이 나무인데, 현재 마력의 양이 10 미만인 경우

 

 

3) 다음칸이 나무인데, 다다음 칸이 나무인 경우

if(board[nr][nc] == 1) {	//벽인 경우 현재 방향기준 다다음칸이 벽이 아니라면 다다음칸으로 지나갈 수 있다.
	int nnr = nr + dr[d];
	int nnc = nc + dc[d];
	if(isInRange(nnr, nnc) && board[nnr][nnc] != 1) {
		queue.add(new int[] {nnr, nnc, curWis - 10, cost+1});
	}
}

 

 

---

코드

import java.io.*;
import java.util.*;
class Main {
	private static int R, C, wis;
	private static int[][] board;
	private static int[] dr = {0, 0, 1, -1};
	private static int[] dc = {1, -1, 0, 0}; 
	public static void main(String[] args) throws Exception {
		input();
		int result = bfs();
		System.out.println(result);
	}
	
	private static int bfs() {
		Queue<int[]> queue = new LinkedList<>();
		boolean[][][] visited = new boolean[R][C][wis+1];
		bfsStartSetting(queue, visited);
		
		while(!queue.isEmpty()) {
			int[] cur = queue.poll();
			int row = cur[0], col = cur[1], curWis = cur[2], cost = cur[3];
			
			if(row == R-1 && col == C-1) {
				return cost;
			}
			
			for(int d=0; d<4; d++) {
				int nr = row + dr[d];
				int nc = col + dc[d];
				if(!isInRange(nr, nc)) {
					continue;
				}
				if(visited[nr][nc][curWis]) {
					continue;
				}
				if(board[nr][nc] == 1 && curWis < 10) {
					continue;
				}
				if(board[nr][nc] == 0) {	//빈칸인 경우 지나갈 수 있다.
					queue.add(new int[] {nr, nc, curWis, cost+1});
					visited[nr][nc][curWis] = true;
				} else {	//벽인 경우 현재 방향기준 다다음칸이 벽이 아니라면 다다음칸으로 지나갈 수 있다.
					int nnr = nr + dr[d];
					int nnc = nc + dc[d];
					if(isInRange(nnr, nnc) && board[nnr][nnc] != 1) {
							queue.add(new int[] {nnr, nnc, curWis - 10, cost+1});
							visited[nnr][nnc][curWis-10] = true;
					}
				}
			}
		}
		return -1;
	}
	
	private static boolean isInRange(int r, int c) {
		return 0<=r && r<R && 0<=c && c<C;
	}
	
	private static void bfsStartSetting(Queue<int[]> q, boolean[][][] v) {
		q.add(new int[] {0, 0, wis, 0});	// (r, c, reminWis, cost)
		v[0][0][wis] = true;
	}
	
	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		wis = Integer.parseInt(st.nextToken());
		board = new int[R][C];
		for(int r=0; r<R; r++) {
			String temp = br.readLine();
			for(int c=0; c<C; c++) {
				board[r][c] = (int) temp.charAt(c) - 48;
			}
		}
	}
}