[Java] 2178번 미로탐색

1. 문제 링크 및 문제

https://www.acmicpc.net/problem/2178

1-1 문제 요약

: N*M 크기의 배열에서 , (0,0) 부터 시작하여 (N,M)까지 좌표값이 1인 경우로만 가는데 최단경로

2. 해결 방법 생각해보자 ...

1. 최단경로라면 bfs로 접근해보자
2. BFS(x,y) 시작지점 및 종료시점, 탐색방법 생각해보기
   2-1 시작지점 : 0,0 에서 시작 (= bfs(0,0) )
   2-2 종료시점 : 리턴 x==N,y==M 일 때 리턴 , 아니면 2-3
   2-3 탐색방법 : 방향벡터를 사용하여 상하좌우 탐색

3. 코드

import java.util.LinkedList;
import java.awt.Point;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

    static int N,M;
    static int[][] map;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,1,-1};
    static boolean[][] visited;
    static Queue<Point> q = new LinkedList<>();

    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());

        map = new int[N][M];
        for(int i=0;i<N;i++){
            String s = br.readLine();
            for (int j=0;j<M;j++){
                map[i][j] = s.charAt(j) - '0';
            }
        }
        visited = new boolean[N][M];
        visited[0][0] = true;
        bfs(0,0);
        System.out.println(map[N-1][M-1]);
    }

    public static void bfs(int x, int y){
        int xx, yy;
        q.offer(new Point(x,y));
        while (!q.isEmpty()){
            Point now = q.poll();
            for (int i=0;i<4;i++){
                xx = now.x + dx[i];
                yy = now.y + dy[i];
                if(xx<0 || xx>=N || yy<0 || yy>=M) continue;
                if (map[xx][yy] != 0 && !visited[xx][yy]){
                    q.offer(new Point(xx,yy));
                    map[xx][yy] = map[now.x][now.y]+1;
                    visited[xx][yy] = true;
                }
            }
        }
    }
}

그림으로 이해

아래 그림에서 배열의 값이 어떻게 변하는 지 살펴본다면 이해하기 더 쉬울 것이다

예시 : 백준 예제입력1
4 6
101111
101010
101011
111011

1. 초기상태의 배열

2. bfs(0,0) 그림으로 이해하기

각 문장 이해
1. q:(0,0)
: x,y = q.popleft() 에서 x=0, y=0 이 됨
2. q.append(1,0)
: 상하좌우 중 1 인 좌표를 q에 추가 (여기선 1,0 밖에 없음)
3. map[1][0] = map[0][0]+1
: 해당 좌표를 전 좌표값 + 1 을 해줌

상하좌우 중 1 이 하나밖에 없는 과정은 생략하였음.

q가 (0,4)일 때를 보면 알 수 있듯이, 모든 경로를 탐색하지만 경우의 수에 포함되지 않는다.

! 아차차

실수

파이썬으로 풀다가 자바로 푸니까 헷갈린당
습관처럼 1 로 썼다가 답이 제대로 나오지 않았음 ㅎㅎ

1. map[xx][yy] = map[x][y]+1;

2. map[xx][yy] = map[now.x][now.y]+1;