Last Update : 2022-06-21 00:11:42 +0900
- C++로 재풀이
미로 탐색 (2178번)
https://www.acmicpc.net/problem/2178
풀이방법
- BFS(너비우선탐색)를 이용한 문제풀이
- 무조건 (1,1)에서 (N,M)까지라고 하였으므로 어디서부터 시작해야하는지 찾을 필요 없음
- 시작점에서의 거리를 계산함
- 현재값에서 상하좌우를 확인하고, 현재 거리값에 +1한 값을 상하좌우의 방문하지않았으며 0이 아닌 곳에 입력
distance배열에서 좌표의 값이 -1인 경우 방문하지 않은 곳
Java
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
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
int[][] distance = new int[N][M];
for(int i=0; i<N; i++) {
String str = br.readLine();
for(int j=0; j<M; j++) {
map[i][j] = str.charAt(j) - '0';
distance[i][j] = -1;
}
}
Queue<int[]> queue = new LinkedList<>();
int[] directX = {1, 0, -1, 0};
int[] directY = {0, 1, 0, -1};
int curX = 0;
int curY = 0;
int dx = 0;
int dy = 0;
queue.add(new int[] { 0, 0 });
distance[0][0] = 1;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
curX = cur[0]; curY = cur[1];
for(int i=0; i<4; i++) {
dx = curX + directX[i];
dy = curY + directY[i];
if (dx < 0 || dx >= M || dy < 0 || dy >= N) continue;
if (map[dy][dx] != 0 && distance[dy][dx] == -1) {
distance[dy][dx] = distance[curY][curX]+1;
queue.add(new int[] { dx, dy });
}
}
}
System.out.println(distance[N-1][M-1]);
}
}
C++
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
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
string map[102];
int visit[102][102];
cin >> n >> m;
queue<pair<int, int>> Q;
for (int i=0; i<n; i++) {
cin >> map[i];
}
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
visit[0][0] = 1;
Q.push(pair(0, 0));
while (!Q.empty()) {
pair<int, int> data = Q.front();
Q.pop();
for (int i=0; i<4; i++) {
int x = data.first + dx[i];
int y = data.second + dy[i];
if (x < 0 || y < 0 || x >= n || y >= m) continue;
if (visit[x][y] > 0 || map[x][y] == '0') continue;
visit[x][y] = visit[data.first][data.second] + 1;
Q.push(pair(x, y));
}
}
cout << visit[n-1][m-1];
}
Comments powered by Disqus.