[문제]
N×M크기의 배열로 표현되는 미로가 있다.
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
[입력]
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
[출력]
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
[예제]
>문제 풀이
최단 경로를 찾는 문제라고 해서 BFS로 풀었습니다.
이제 BFS의 동작 원리를 알았을 뿐 이런문제를 처음 풀어봐서, '목적지 까지 가는 경로가 여러개일 경우 어디로 가느냐에 따라 cnt값도 달라질텐데, 재귀를 쓰지않고 cnt를 어떻게 따로 저장해둘지'에서 막혔었습니다.
(그래서 로직이 같고, 문제점을 해결한 다른 분들의 코드를 참조하여 공부하였습니다.)
방문한 mat[][]들을 이전 mat[][]값으로 부터 누적 카운팅 해서 최종적으로는 mat[N-1][M-1]을 출력하도록 했습니다.
+)그리고 이차 배열의 인덱스 값을 큐에 저장해야하기 때문에 x값 y값을 순서대로 offer, poll하도록 구현했습니다.
변수는 nx(now x값)= x(이전 위치x값)+ dx(x값의 변화량); 이런 의미로 넣었습니다.
public static void bfs(int x, int y) {
int[] dx= {-1, 0, 0, 1};
int[] dy= {0, -1, 1, 0};
int nx, ny;
Queue<Integer> que= new LinkedList<Integer>();
que.offer(x);
que.offer(y);
visited[x][y]=1;
cnt++;
while(!que.isEmpty()) {
x=que.poll();
y=que.poll();
for(int j=0; j<4; j++) {
nx= x+dx[j];
ny= y+dy[j];
if(nx>=0&&nx<N&&ny>=0&&ny<M) {
if(mat[nx][ny]>0&&visited[nx][ny]!=1) {
visited[nx][ny]=1;
mat[nx][ny]= mat[x][y]+1;
que.offer(nx);
que.offer(ny);
}
}//if
}
}//while
}//bfs
>전체 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N, M, cnt=0;
static int visited[][], mat[][];
public static void main(String [] args) {
Scanner scan= new Scanner(System.in);
N= scan.nextInt();
M= scan.nextInt();
visited= new int[N][M];
mat= new int[N][M];
String str;
for(int i=0; i<N; i++) {
str= scan.next();
for(int j=0; j<M; j++) {
mat[i][j]= Integer.parseInt(str.charAt(j)+"");
}
}
bfs(0,0);
System.out.println(mat[N-1][M-1]);
}
public static void bfs(int x, int y) {
int[] dx= {-1, 0, 0, 1};
int[] dy= {0, -1, 1, 0};
int nx, ny;
Queue<Integer> que= new LinkedList<Integer>();
que.offer(x);
que.offer(y);
visited[x][y]=1;
cnt++;
while(!que.isEmpty()) {
x=que.poll();
y=que.poll();
for(int j=0; j<4; j++) {
nx= x+dx[j];
ny= y+dy[j];
if(nx>=0&&nx<N&&ny>=0&&ny<M) {
if(mat[nx][ny]>0&&visited[nx][ny]!=1) {
visited[nx][ny]=1;
mat[nx][ny]= mat[x][y]+1;
que.offer(nx);
que.offer(ny);
}
}//if
}
}//while
}//bfs
}2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
| [백준 알고리즘]1697번: 숨바꼭질_Java (0) | 2021.05.04 |
|---|---|
| [백준 알고리즘]7576번: 토마토_Java (0) | 2021.04.30 |
| [백준 알고리즘]1012번: 유기농 배추_Java (0) | 2021.04.27 |
| [백준 알고리즘]2667번 단지번호 붙이기_Java (DFS풀이) (0) | 2021.04.26 |
| [백준 알고리즘] 2606번 바이러스_Java (0) | 2021.04.24 |
