[JAVA 01] 2178. 미로찾기

2178. 미로찾기 (S1) 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답
1 초	192 MB	211768	97792	61944	44.611%

 

문제

 

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

---

 

summary

(1,1) 부터 (N,M) 까지 최소 이동 칸 수 구하기.

 

- 서로 인접한 칸만 이동 가능

- (N,M) 항상 도착 가능

 

strategy

최소 이동 거리를 구하기 위해서 완전탐색 방법 중 너비 우선 탐색(Queue)으로 진행. 

 

- 이미 방문한 곳 여부 체크 (visited)

- 이동 칸수 체크 (visited)

- 벽인지 체크 (map)

note

- N, M(2 ≤ N, M ≤ 100)

 

import java.util.*;
import java.io.*;
import java.awt.Point;

public class Main {
    
    static int dir[][] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    
    static int N = 0, M = 0, answer = 0;
    static int[][] map;
    static int [][] visited;
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        /* input */
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new int[N][M];

        for (int n = 0; n < N; n++) {
            String[] s = br.readLine().split("");
            for (int m = 0; m < M; m++) {
                map[n][m] = Integer.parseInt(s[m]);
            }
        }

        /* logic */
        answer = BFS();
        
        /* output */
        System.out.println(answer); 

        br.close();
    }

    public static int BFS() {
        Queue<Point> q = new ArrayDeque<>();
        
        visited[0][0] = 1;
        q.add(new Point(0,0));
        

        while(!q.isEmpty()) {
            Point current = q.poll();
            
            for(int[] d : dir) {
                int mx = current.x + d[0];
                int my = current.y + d[1];

                if(mx < 0 || mx >= N || my < 0 || my >= M) continue; // map index range
                if(map[mx][my] == 0 || visited[mx][my] != 0) continue; // 벽, 방문 여부 확인

                visited[mx][my] = visited[current.x][current.y] + 1; // 방문처리
                q.add(new Point(mx, my)); 
            }

            if(current.x == N-1 && current.y == M-1) break; // 도착 했으면 즉시 종료
        }
        return visited[N-1][M-1];
    }
}

 

문제	결과	메모리	시간	언어코드	길이
2178	맞았습니다!!	16596	156	Java 11 / 수정	1831

 

 

MEMO

- BFS 에서 while(q,isEmpty())  실수 주의  > while(!q,isEmpty()) 

- 시작점도 방문 처리 까먹지 말기