Post

BaekJoon : 2178(미로 탐색)

Posted
By splin
11 min read
BaekJoon : 2178(미로 탐색)

Java : BaekJoon Navigation

BaekJoon Navigation(탐색) 저의 문제풀이 입니다.

혹시 더 좋은 방법 알려주신다면 정말 감사하겠습니다!

2178

N×M크기의 배열로 표현되는 미로가 있다.

101111
101010
101011
111011

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

1
2
3
4
5
6

4 6		// 미로의 크기 n,m을 입력합니다
101111
101010
101011
111011	// 각각의 수들을 붙여서 미로를 만듭니다.
15		// (n,m)의 위치로 이동할 수 있는 최단 거리를 출력합니다

방법1

최단 거리를 구하는 것이기 때문에 하나를 깊숙히 탐색하는 DFS보다는 레벨 단위로 체크를 해서 레벨의 깊이를 이용해 거리를 구할 수 있는 BFS를 이용해야 합니다. Node 클래스를 만들고 인접리스트로 BFS를 수행하면서 깊이를 체크하는 방식으로 풀었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static InputStreamReader isr = new InputStreamReader(System.in);
	static BufferedReader br = new BufferedReader(isr);
	
	// 행과열정보, 길인지 벽인지 체크하는 변수, 인접노드 리스트를 가지고 있는 노드 클래스
	public static class Node {
		boolean checkRoad;
		int row;
		int col;
		List<Node> adjacentNodes;
		
		public Node(int row, int col, boolean checkRoad) {
			adjacentNodes = new ArrayList<>();
			this.row = row;
			this.col = col;
			this.checkRoad = checkRoad;
		}
		
		public void add(Node node) {
			adjacentNodes.add(node);
		}
	}
	
	// 미로를 만들어주면서 노드 클래스 인접노드 리스트에 노드를 넣어줍니다.
	public static Node[][] MakeMaze(int n, int m) throws Exception {
		Node maze[][] = new Node[n][m];
		
		for (int i = 0; i < maze.length; i++) {
			char wallsOrRoads[] = br.readLine().trim().toCharArray();  
			
			for (int j = 0; j < wallsOrRoads.length; j++) {
				boolean checkRoad = false;
				if(wallsOrRoads[j] == '1')
					checkRoad = true;
					
				maze[i][j] = new Node(i, j, checkRoad);
				
				// i 즉, 행이 0이 아니면 현재 행열 위에 있는 길 노드를 인접노드에 저장합니다.
				// 위에만 저장한 이유는 인접리스트에 서로 추가해 주기 때문입니다. 
				if(i != 0)
					if(maze[i-1][j].checkRoad && maze[i][j].checkRoad) {
						maze[i-1][j].add(maze[i][j]);
						maze[i][j].add(maze[i-1][j]);
					}
				
				// j 즉, 열이 0이 아니면 현재 행열 왼쪽에 있는 길 노드를 인접노드에 저장합니다.
				if(j != 0)
					if(maze[i][j-1].checkRoad && maze[i][j].checkRoad) {
						maze[i][j-1].add(maze[i][j]);
						maze[i][j].add(maze[i][j-1]);
					}
			}
		}
		return maze;
	}
	
	// Node클래스안에 인접리스트를 이용한 BFS입니다. int형을 반환하는데, 이 때 반환 값은 depth를 의미합니다.
	public static int BFS(Node startNode,Node findNode,int n, int m) {
		boolean checkNodes[][] = new boolean[n][m];
		
		Queue<Node> queue = new LinkedList<>();
		queue.add(startNode);
		checkNodes[startNode.row][startNode.col] = true;	
		Node checkNode; 
		
		// depth를 체크하기 위한 변수 처음에 startNode가 들어갔기 때문에 1로시작합니다.
		int depth = 1;
		// 한 레벨에서 체크하지 않은 노드의 수 입니다.
		int countNodesInLevel = 1;
		// 현재 레벨의 다음레벨의 노드 수를 저장합니다.
		int countAdjacentNodes = 0;
		
		while(!queue.isEmpty()) {
			checkNode = queue.poll();	
			// 큐에서 하나를 빼면서 체크할 것이기 때문에 --를 해줍니다.
			--countNodesInLevel;
					
			if(checkNode == findNode) {
				break;
			}

			// 체크노드의 인접노드들을 순회하면서 체크되지 않은 노드들은 큐에 넣어주고 체크해줍니다.
			// 이 때, 큐에 넣는 순간 countAdjacentNodes값을 ++ 해줍니다.
			// 이렇게 해주는 이유는 특정 레벨의 다음 레벨의 수를 구해주기 위함입니다.
			for(Node node : checkNode.adjacentNodes) {
				if(!checkNodes[node.row][node.col]) {
					queue.add(node);
					checkNodes[node.row][node.col] = true;
					++countAdjacentNodes;
				}
			}
			
			// countNodesInLevel이 0이 될 때, 즉 현재 레벨을 다 체크하였으면 다음레벨의 노드 수를 넣어주고
			// 다음 레벨의 노드수는 0으로 다시 초기화하고 depth를 1올려줍니다.
			if(countNodesInLevel == 0) {
				countNodesInLevel = countAdjacentNodes;
				countAdjacentNodes = 0;
				++depth;
			}
		}
		return depth;
	}
	
	public static void main(String[] args) {
		OutputStreamWriter osw = new OutputStreamWriter(System.out);
		BufferedWriter bw = new BufferedWriter(osw);
		
		try {
			String mazeSize = br.readLine().trim();
			StringTokenizer stk = new StringTokenizer(mazeSize);
			
			int n = Integer.parseInt(stk.nextToken());
			int m = Integer.parseInt(stk.nextToken());
			
			Node maze[][] = MakeMaze(n, m);
			
			int result = BFS(maze[0][0],maze[n-1][m-1], n, m);
			
			bw.write(Integer.toString(result));
			bw.flush();
			bw.close();
			
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

방법2

미로 행렬의 값을 레벨로 표시해서 값을 구하는 방식입니다. BFS에서 상하좌우를 체크해서 인접행렬을 체크하고 다음레벨의 행렬의 값을 올려주면서 해당행렬의 값이 레벨(깊이)을 가지게 해서 최단거리를 구합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static InputStreamReader isr = new InputStreamReader(System.in);
	static BufferedReader br = new BufferedReader(isr);
	// static 함수에서 사용할 수 있게 static으로 정의하였습니다.
	static int maze[][];
	static boolean check[][];
	static int n,m;
		
	// 미로를 입력 받고 만들어줄 함수
	public static void MakeMaze() throws Exception {
		maze = new int[n][m];
		check = new boolean[n][m];
		
		for (int i = 0; i < maze.length; i++) {
			char wallsOrRoads[] = br.readLine().trim().toCharArray();  
			
			for (int j = 0; j < wallsOrRoads.length; j++) {
					maze[i][j] = wallsOrRoads[j] - 48;
			}
		}
	}
	
	// BFS 함수. 찾는 행열의 레벨(최단 거리)를 반환해줍니다. 
	// 다음 레벨로 가면 미로안의 숫자를 +1 해서 레벨 표시를 해주는 방식입니다.
	// 예를들어 (0,0)부터 시작하고 (1,0)이 갈수 있는 미로(1)이면
	//  maze[1][0] = maze[0][0] + 1 을 해주어서 레벨 2라고 표현해 주는 것입니다.
	public static int BFS(int findRow, int findCol) {
		// 미로의 상하좌우를 체크할 때 사용할 배열 입니다.
		int dirRow[] = {-1, 1, 0, 0};
		int dirCol[] = {0, 0, -1, 1};
		
		Queue<Integer> rowQueue = new LinkedList<>();
		Queue<Integer> colQueue = new LinkedList<>();
		
		rowQueue.add(0);
		colQueue.add(0);
		check[0][0] = true;
		
		while(!rowQueue.isEmpty()) {
			
			int row = rowQueue.poll();
			int col = colQueue.poll();
			
			// 상하좌우를 체크해줍니다.
			for (int i = 0; i < dirRow.length; i++) {
				
				int tmpRow = row + dirRow[i];
				int tmpCol = col + dirCol[i];
				
				// 범위 안의 미로만 체크할 수 있게 하는 것입니다. 
				// 예를 들어, (-1,0) 이나 행이나 열의 값이 n,m을 넘지 않게 하는 것입니다.
				if(tmpRow >= 0 && tmpCol >= 0
						&& tmpRow < n && tmpCol < m) {
					// 아직 체크되지 않는 행열이고 갈 수 있는 미로면 큐에 넣어주고 체크 후, 레벨을 올려줍니다.
					if(!check[tmpRow][tmpCol] && maze[tmpRow][tmpCol] == 1) {
						
						rowQueue.add(tmpRow);
						colQueue.add(tmpCol);
						
						check[tmpRow][tmpCol] = true;
						maze[tmpRow][tmpCol] = maze[row][col] + 1;
					}
				}
				
			}
		}
		return maze[findRow][findCol];
	}
	
	public static void main(String[] args) {
		OutputStreamWriter osw = new OutputStreamWriter(System.out);
		BufferedWriter bw = new BufferedWriter(osw);
		
		try {
			String mazeSize = br.readLine().trim();
			StringTokenizer stk = new StringTokenizer(mazeSize);
			
			n = Integer.parseInt(stk.nextToken());
			m = Integer.parseInt(stk.nextToken());
			
			MakeMaze();
			
			int result = BFS(n-1,m-1);
			
			bw.write(Integer.toString(result));
			bw.flush();
			bw.close();
			
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

해당 코드들은 저의 GitHub에서 확인할 수 있습니다.

Coding Test, BaekJoon
Coding Test BaekJoon BaekJoon : Navigation
This post is licensed under CC BY 4.0 by the author.