4x6 크기의 배열로 표현되는 다음과 같은 미로가 있다.
미로의 각 칸에 들어 잇는 숫자 중 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타낸다. 한 칸에서 다른 칸으로 이동할 때는 서로 인접한 칸으로만 이동할 수 있다. 이동한 칸을 셀 때는 시작 위치와 도착 위치를 포함한다. 즉 (1,1)에서 (4,6)으로 이동하려면 총 15칸을 지나가야 한다.
NxM 크기의 미로가 주어질 때 (1,1)에서 출발해 (NxM)의 위치로 이동하기 위해 지나야 하는 칸 수의 최솟값을 구하는 프로그램을 작성하시오.
(시간 제한 1초)
입력
1번째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100), 그 다음 N개의 줄에는 미로의 내용이 M개의 정수로 주어진다. 각각의 수들은 붙어서 입력된다.
출력
1번째 줄에 지나야 하는 칸 수의 최솟값을 출력한다. 항상 도착 위치로 이동할 수 있을 때만 입력으로 주어진다.
예제 입력
4 6 // N, M
110110
110110
111111
111101
예제 출력
91단계 - 문제 분석하기
N, M의 최대 크기가 100으로 매우 작기 때문에 시간 제한은 별도로 생각하지 않아도 된다.
문제의 요구사항은 지나야 하는 칸 수의 최솟값을 찾는 것이다. 이는 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지를 구하는 것과 동일하다. 따라서 BFS를 사용해 최초로 도달했을 때 깊이를 출력하면 문제를 해결할 수 있다.
DFS보다 BFS가 적합한 이유는 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문이다.
2단계 - 손으로 풀어 보기
먼저 2차원 배열 데이터를 저장한 다음 (1,1)에서 BFS를 실행한다. 상,하,좌,우 네 방향을 보며 인접한 칸을 본다. 인접한 칸의 숫자가 1이면서 아직 방문하지 않았다면 큐에 삽입한다. 종료 지점 (N,M)에서 BFS를 종료하며 깊이를 출력한다.
그림을 보면 (1,1) 에서 출발해 상,하,좌,우 순서로 노드를 삽입하며 방문 배열에 체크한다.
시작 부분의 경우 하,우 만 방문할 수 있으므로 하,우 순서로 노드를 큐에 삽입한다.
이런 방식으로 노드를 방문하면 깊이 9단계에서 (4,6)에 도달한다.
3단계 - sudo코드 작성하기
dx, dy(상하좌우를 탐색하기 위한 define값 정의 변수)
A(데이터 저장 2차원 행렬)
N(row), M(column)
visited(방문 기록 저장 배열)
A 배열 초기화하기
visited 배열 초기화하기
for(N의 개수만큼 반복)
{
for(M의 개수만큼 반복)
{
A 배열에 데이터 저장하기
}
}
BFS(0, 0) 실행
A[N-1][M-1] 값 출력
BFS {
큐 자료구조에 시작 노드 삽입(add)
visited 배열에 현재 노드 방문 기록
while(큐가 비어 있을 때까지)
{
큐에서 노드 데이터를 가져오기(poll)
for(상하좌우 탐색)
{
if(유효한 좌표)
{
if(이동할 수 있는 칸이면서 방문하지 않은 노드)
{
visited 배열에 방문 기록하기
A배열에 depth를 현재 노드의 depth+1 로 업데이트하기
큐에 데이터 삽입하기(add)
}
}
}
}
}4단계 - 코드 구현하기
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 Q27 {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static boolean[][] visited;
static int[][] A;
static int N, M;
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[N][M];
visited = new boolean[N][M];
for(int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine());
String line = st.nextToken();
for(int j = 0; j < M; j++){
A[i][j] = Integer.parseInt(line.substring(j, j+1));
}
}
BFS(0, 0);
System.out.println(A[N-1][M-1]);
}
public static void BFS(int i, int j) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {i,j});
visited[i][j] = true;
while (!queue.isEmpty()){
int now[] = queue.poll();
for(int k = 0; k < 4; k++){
int x = now[0] + dx[k];
int y = now[1] + dy[k];
if(x >= 0 && y >= 0 && x < N && y < M){ // 좌표 유효성 검사
if(A[x][y] != 0 && !visited[x][y]){
visited[x][y] = true;
A[x][y] = A[now[0]][now[1]] + 1;
queue.add(new int[] {x, y});
}
}
}
}
}
}
- Do it! 알고리즘 코딩테스트 자바 편
