99클럽 코테 스터디 15일차 TIL (챌린저): [백준][Java] 2665 미로만들기 - 골드4

 

문제 보기

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

 

 

풀이

bfs에 다익스트라 논리를 적용하면 풀 수 있다.

특정 칸 까지 걸리는 최소 검은 방을 최단거리로 생각하면 된다.

 

int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Queue<int[]> q = new LinkedList<>();
int[][] dist = new int[N][N];
for(int i = 0; i < N; i++) {
  for(int j = 0; j < N; j++) {
    dist[i][j] = -1;
  }
}
q.add(new int[]{0, 0, 0});
dist[0][0] = 0;

while(!q.isEmpty()) {
  int[] cur = q.poll();
  for(int k = 0; k < 4; k++) {
    int x = cur[0] + dx[k];
    int y = cur[1] + dy[k];

    if(x < 0 || y < 0 || x >= N || y >= N) continue;
    if(matrix[x][y]) {
      if(dist[x][y] == -1 || dist[x][y] > cur[2] + 1) {
        dist[x][y] = cur[2] + 1;
        q.add(new int[]{x, y, dist[x][y]});
      }
    } else {
      if(dist[x][y] == -1 || dist[x][y] > cur[2]) {
        dist[x][y] = cur[2];
        q.add(new int[]{x, y, dist[x][y]});
      }
    }
  }
}

그래서 코드를 보면 별 게 없다.

dist 배열을 -1로 초기화 한다.

도착한 칸이 검은 방일 경우, 그 칸의 최소 검은 방이 현재 최소 검은 방 + 1보다 크면 갱신

흰 방일 경우 최소 검은 방이 현재 최소 검은 방보다 크면 갱신

-1 경우는 무조건 갱신이다.

 

간단한 다익스트라 논리를 적용해 풀었기 때문에 코드를 보면 바로 이해할 것 같다!

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    boolean[][] matrix = new boolean[N][N];
    for(int i = 0; i < N; i++) {
      String line = br.readLine();
      for(int j = 0; j < N; j++) {
        matrix[i][j] = line.charAt(j) == '0';
      }
    }

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    Queue<int[]> q = new LinkedList<>();
    int[][] dist = new int[N][N];
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        dist[i][j] = -1;
      }
    }
    q.add(new int[]{0, 0, 0});
    dist[0][0] = 0;

    while(!q.isEmpty()) {
      int[] cur = q.poll();
      for(int k = 0; k < 4; k++) {
        int x = cur[0] + dx[k];
        int y = cur[1] + dy[k];

        if(x < 0 || y < 0 || x >= N || y >= N) continue;
        if(matrix[x][y]) {
          if(dist[x][y] == -1 || dist[x][y] > cur[2] + 1) {
            dist[x][y] = cur[2] + 1;
            q.add(new int[]{x, y, dist[x][y]});
          }
        } else {
          if(dist[x][y] == -1 || dist[x][y] > cur[2]) {
            dist[x][y] = cur[2];
            q.add(new int[]{x, y, dist[x][y]});
          }
        }
      }
    }
    bw.write(dist[N - 1][N - 1] + "\n");

    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/2665.%E2%80%85%EB%AF%B8%EB%A1%9C%EB%A7%8C%EB%93%A4%EA%B8%B0

CodingTest_AutoSave/백준/Gold/2665. 미로만들기 at main · MetroDefro/CodingTest_AutoSave