[백준] 2206번 벽 부수고 이동하기 / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
24. DFS와 BFS
그래프를 순회하는 알고리즘을 배워 봅시다.
그래프를 순회하는 알고리즘을 배워 봅시다.
Java / Python
9. 벽 부수고 이동하기
"현재 상태"를 정점으로 표현하여 그래프를 만들고 최단거리를 구하는 문제
이번 문제는 NxM의 행렬로 표현되는 맵이 주어질 때, 최단 경로를 구하는 프로그램을 작성하는 문제입니다.
BFS 탐색을 이용했습니다.
- Java
import java.io.*;
import java.util.*;
public class Main {
static class Point{
int x;
int y;
int dist; // 이동 거리
int drill; // 공사 횟수
public Point(int x, int y, int dist, int drill){
this.x = x;
this.y = y;
this.dist = dist;
this.drill = drill;
}
}
static int N, M;
static int result;
static int[][] map, check;
static int[] dx = {0,0,-1,1};
static int[] dy = {-1,1,0,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
check = 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] = Integer.parseInt(String.valueOf(str.charAt(j)));
check[i][j] = Integer.MAX_VALUE;
}
}
result = Integer.MAX_VALUE;
bfs(0,0);
if (result == Integer.MAX_VALUE) {
bw.write("-1\n");
} else {
bw.write(result + "\n");
}
bw.flush();
bw.close();
br.close();
}
public static void bfs(int x, int y) {
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(x, y, 1, 0));
check[y][x] = 0;
while (!queue.isEmpty()) {
Point p = queue.poll();
if(p.x == M - 1 && p.y == N - 1){
result = p.dist;
break;
}
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
if (check[ny][nx] > p.drill) {
if (map[ny][nx] == 0) {
queue.add(new Point(nx, ny, p.dist + 1, p.drill));
check[ny][nx] = p.drill;
}else{
if(p.drill == 0){
queue.add(new Point(nx, ny, p.dist + 1, p.drill + 1));
check[ny][nx] = p.drill + 1;
}
}
}
}
}
}
}
}
- Python
from collections import deque
import sys
N, M = map(int, sys.stdin.readline().split())
place = [list(map(int, input())) for _ in range(N)]
check = [[[0]*2 for _ in range(M)] for _ in range(N)]
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
# bfs 경로 탐색
def bfs():
queue = deque()
queue.append([0, 0, 1])
check[0][0][1] = 1
while queue:
a, b, w = queue.popleft()
if a == N - 1 and b == M - 1:
return check[a][b][w]
for i in range(4):
x = a + dx[i]
y = b + dy[i]
if 0 <= x < N and 0 <= y < M:
if place[x][y] == 1 and w == 1:
check[x][y][0] = check[a][b][1] + 1
queue.append([x, y, 0])
elif place[x][y] == 0 and check[x][y][w] == 0:
check[x][y][w] = check[a][b][w] + 1
queue.append([x, y, w])
return -1
print(bfs())
Author And Source
이 문제에 관하여([백준] 2206번 벽 부수고 이동하기 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-2206번-벽-부수고-이동하기-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)