문제
미로의 (1,1) 에서 (n,m)위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다.
BFS + DP를 이용하여 해결하였다.
해결 방안
1. 미로의 이동 가능 여부 관련 값은 maps[][]에 저장하였다.(1이면 이동 가능)
미로의 해당 칸으로 이동할 때 지나야하는 최소의 칸 수는 cnts[][]에 저장하였다.(0이면 한번도 이동 안한 곳)
2. 주어진 maps의 (1,1) 위치에서 (m,n)으로 BFS 방법으로 4방향을 탐색하고 DP를 이용하여 cnts에 지나야하는 최소 칸 수를 메모제이션하였다.
3. cnts[n][m]을 출력하면 도착 위치에 가기위해 지나야하는 최소의 칸을 출력한다.
코드
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 n; // 세로
static int m; // 가로
static int[][] maps;
static int[][] cnts; // 이동할 때 최소 칸수
// 북 동 남 서
static int[] dy = {-1, 0, 1, 0}; // 세로
static int[] dx = {0, 1, 0, -1}; // 가로
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
n = Integer.parseInt(str.split(" ")[0]);
m = Integer.parseInt(str.split(" ")[1]);
maps = new int[n+1][m+1];
cnts = new int[n+1][m+1];
StringTokenizer st;
for(int i=1; i<n+1; i++) {
str = br.readLine();
for(int j=1; j<m+1; j++) {
maps[i][j] = Integer.parseInt(str.split("")[j-1]);
}
}
// == 입력 끝
bfs();
// 도착위치(n,m) 의 최소 칸 수
System.out.println(cnts[n][m]);
}
static void bfs() {
Queue<int[]> q = new LinkedList<>();
// 1,1에서 시작
q.offer(new int[]{1,1});
cnts[1][1] = 1;
// 세로, 가로
int[] current = new int[2];
int[] next = new int[2];
while(!q.isEmpty()) {
current = q.poll();
// 4방향의 인접 위치
for(int i=0; i<4; i++) {
next[0] = current[0] + dy[i];
next[1] = current[1] + dx[i];
// 범위 안에 있고 이동할 수 있는 곳이고(map[][]==1) 방문한 적 없을 때(cnts[][]==0)
if(next[0]>0 && next[1]>0 && next[0]<=n && next[1]<=m && maps[next[0]][next[1]]==1 && cnts[next[0]][next[1]]==0) {
q.offer(new int[] {next[0], next[1]});
cnts[next[0]][next[1]] = cnts[current[0]][current[1]]+1;
}
}
}
}
}
'Old > Algorithms' 카테고리의 다른 글
| [JAVA] 백준 2667번 : 단지번호붙이기(DFS) (0) | 2020.10.21 |
|---|---|
| [JAVA] 백준 1012번 : 유기농 배추(DFS) (0) | 2020.10.15 |
| [JAVA] 백준 2606번 : 바이러스 (DFS) (0) | 2020.10.13 |
| [JAVA] 백준 10974번 : 모든 순열 (DFS) (0) | 2020.10.13 |
| [JAVA] 백준 1697번 : 숨바꼭질(BFS) (0) | 2020.10.12 |
