99클럽 코테 스터디 14일차 - 백준 , 미로만들기

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 

문제

풀이

문제 해석

1. n x n 크기의 방이 검은색, 흰색으로 채워져 있다.

2. 검은색은 지나갈 수 없다.

3. 0,0에서 n-1, n-1까지 가야 한다.

4. 검은 방을 최소로 지나도록 하려고 한다.

5. 최솟값을 출력해라

문제 풀이

1. 최단거리문제이므로 BFS를 사용한다.

2. 지나가면서 검은 방을 만나면 부시고 개수를 세고 기록한다.

3. 모든 경로를 탐색하고 도착지점에 최솟값이 저장되었으므로 그곳의 값을 출력한다.

소스코드

package online.judge.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * 미로만들기
 * 골드 4
 */
public class No2665 {
    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] room = new int[n][n];
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                room[i][j] = str.charAt(j) - '0';
            }
        }

        System.out.println(bfs(room, n));

    }

    private static int bfs(int[][] room, int n) {

        Queue<int[]> que = new ArrayDeque<>();
        int[][] visited = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        que.offer(new int[]{0,0,0});


        while(!que.isEmpty()){
            int[] current = que.poll();

            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

                //방문 할 곳이 현재 검은 방보다 크면 갱신
                if(current[2] < visited[nx][ny]){
                    visited[nx][ny] = current[2];
                }else {
                    continue;
                }

                //다음 방문 할 방이 검은 방이면 1추가
                if(room[nx][ny] == 0){
                    que.offer(new int[]{nx,ny,current[2] + 1});
                }else{
                    que.offer(new int[]{nx,ny,current[2]});
                }
            }
        }

        return visited[n-1][n-1];
    }
}

 

 

TIL

• 풀이했던 문제라 간단하게 풀었다.