문제
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제 입력1
Copy 4 6
101111
101010
101011
111011 예제 출력1
예제 입력2
Copy 4 6
110110
110110
111111
111101 예제 출력2
예제 입력3
Copy 2 25
1011101110111011101110111
1110111011101110111011101 예제 출력3
예제 입력 4
Copy 7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111 예제 출력 4
풀이
일단 bfs이란 무엇인가에 대해서 이론적으로 확인해보았다.
기본 문제같은 경우이기 때문에 암기가 가장 좋을 것 같다고 생각되어서 이해가 되는대로 문제를 참고해서 풀어보았다.
Copy import java.util.*;
import java.io.*;
public class Main{
static int[][] arr;
static int n, m;
static boolean[][] visited;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
visited[0][0] = true;
for(int i=0; i<n; i++){
String str = br.readLine();
for(int j=0; j<m; j++){
arr[i][j] = str.charAt(j) - '0';
}
}
bfs(0,0);
System.out.println(arr[n-1][m-1]);
}
public static void bfs(int x, int y){
Queue<int[]> q = new LinkedList<int[]>();
//현재 좌표를 넣어주고
q.add(new int[] {x, y});
//이동할 수 있는 가지 수, 동서남북
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
while(!q.isEmpty()){
int[] xy = q.poll();
for(int i=0; i<4; i++){
//동서남북으로 탐색
int nextX = xy[0] + dx[i];
int nextY = xy[1] + dy[i];
//만약 다음으로 넘어가는 곳이 미로를 벗어나거나
//이미 탐색했던 곳이거나 벽이라면 다음 반복문으로 넘어가고
if(nextX<0 || nextX>=n || nextY<0 || nextY>=m
|| visited[nextX][nextY] || arr[nextX][nextY]==0)
continue;
//다음 탐색 지점을 큐에 넣고
q.add(new int[] {nextX, nextY});
//탐색했다고 기록을 찍어두고
visited[nextX][nextY] = true;
//다음 탐색 지점에 현재 탐색지점+1해서 넣어주자
arr[nextX][nextY] = arr[xy[0]][xy[1]]+1;
}
}
}
} 클ㅡ
Copy //클래스를 만들어서 문제를 해결하는 방법도 괜찮은 방법이라고 생각해서 다시 복습겸 연습중이다.
import java.util.*;
import java.io.*;
public class Main{
static int n, m;
static int[][] arr;
static boolean[][] visited;
static int[] dx = {0,1,0,-1};
static int[] dy = {1,0,-1,0};
public static class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
for(int i=0; i<n; i++){
String t = br.readLine();
for(int j=0; j<m; j++){
arr[i][j] = t.charAt(j)-'0';
}
}
fn(new Point(0,0));
System.out.println(arr[n-1][m-1]);
}
public static void fn(Point point){
Queue<Point> q = new LinkedList<>();
q.add(point);
visited[point.x][point.y] = true;
while(!q.isEmpty()){
Point tmp = q.poll();
for(int i=0; i<4; i++){
int nx = tmp.x + dx[i];
int ny = tmp.y + dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=m || visited[nx][ny] || arr[nx][ny]!=1)
continue;
q.add(new Point(nx, ny));
visited[nx][ny] = true;
arr[nx][ny] = arr[tmp.x][tmp.y]+1;
}
}
}
}