BOJ_2178_미로 탐색

1

구분: 그래프 이론, 그래프 탐색, BFS
언어: Java

전략:

BFS 풀어야 하는 이유 - 최단 거리를 구해야 하는데 DFS는 깊게 탐색하니까 비효율적이다. 시간 초과 

방법1 - 내가 다녀온 곳들을 1씩 증가 - 최종 도착지에 도달했을 때의 그 숫자가 정답

방법 2 - 내가 방문한 곳들을 확인하는 boolean 배열이용해서 방문여부 확인. 큐에 좌표와 level도 함께 넣는다. 

인접한 곳에 level을 1씩 증가한다.

---

2. 코드

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

public class Main {
	static int h, w;
	static int[][] map;
	static boolean[][] check;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		h = Integer.parseInt(st.nextToken());
		w = Integer.parseInt(st.nextToken());
		map = new int[h][w];
		check = new boolean[h][w];
		for(int i = 0; i<h; i++) {
			String str = br.readLine();
			for(int j = 0; j<w; j++) {
				map[i][j] = str.charAt(j)-'0';
			}
		}
		
		//int result = bfs(0,0);
		//System.out.println(result);
		
		bfs2(0,0,1);
		//System.out.println(lev);

	}//main
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static class Node{
		int y;
		int x;
		Node(int y, int x){
			this.x = x;
			this.y = y;
		}
	}
	
	static class Node2{
		int x;
		int y; 
		int level;
		Node2(int y, int x, int level){
			this.y = y;
			this.x = x;
			this.level = level;
		}
	}
	
	private static int bfs(int y, int x) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(y, x));
	
		while(!q.isEmpty()) {
			Node node = q.poll();
			int qy = node.y;
			int qx = node.x;
			for(int d = 0; d<4; d++) {
				int nx = qx + dx[d];
				int ny = qy + dy[d];
				
				if(nx<0 || ny<0 ||nx>=w|| ny>=h || map[ny][nx]==0)
					continue;
				if(map[ny][nx]==1) {
					q.offer(new Node(ny, nx));
					map[ny][nx] = map[qy][qx]+1;
				}
			}
		}
		
		return map[h-1][w-1];
	}


	private static void bfs2(int y, int x, int level) {
		Queue<Node2> q = new LinkedList<>();
		q.offer(new Node2(y, x, level));
		check[y][x] = true;
		while(!q.isEmpty()) {
			Node2 node = q.poll();
			int qy = node.y;
			int qx = node.x;
			int lev = node.level;
			for(int d = 0; d<4; d++) {
				int nx = qx + dx[d];
				int ny = qy + dy[d];
				
				//범위 벗어나거나 0이거나 이미 방문한 곳이면 그냥 지나가 
				if(nx<0 || ny<0 ||nx>=w|| ny>=h || map[ny][nx]==0 ||check[ny][nx])
					continue;
				//내가 원하는 곳에 도달하면 정답 출력
				if(!check[ny][nx]&& nx == w-1 && ny == h-1 && map[ny][nx]==1) {
									
					System.out.println(lev+1);
					return;
				}
				//일반적일 경우 그냥 레벨1 증가해서 큐에 삽입
				q.offer(new Node2(ny,nx,lev+1));
				check[ny][nx] = true;
				
				
			}
		}
		
		
	}
	
}

---

3

BFS를 연습하기 좋은 문제이다.