1 minute read

πŸ“Œ λ‚œμ΄λ„

πŸ₯ˆ Silver 1


πŸ“Œ 문제

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

image

image


πŸ“Œ 풀이

이 λ¬Έμ œλ„ 처음 보자마자 λ“  생각은 λ°”λ‘œ 벽이 μ•„λ‹Œ λ°”λ‹₯ μœ„μΉ˜μ—λŠ” μ§€κΈˆκΉŒμ§€ κ±Έλ¦° μ‹œκ°„μ„ μ§‘μ–΄λ„£μž!! λΌλŠ” μƒκ°μ΄μ—ˆλ‹€.
κ·Έλž˜μ„œ 전에 ν‘Ό λ¬Έμ œμ™€ λ˜‘κ°™μ€ λ°©μ‹μœΌλ‘œ ν’€μ—ˆλ‹€.

일단 값을 λ°›μ„λ•Œ, 0인 값은 -1둜 λŒ€μ²΄ν•˜μ—¬ λ„£κ³ , 1은 0으둜 넣은후, Start와 endλΌλŠ” final int ν˜•μ‹μœΌλ‘œ 각각 1κ³Ό -2을 λ„£μ–΄μ€€ 이후, Queue에 1을 λ„£μ—ˆλ‹€.
while(!q.isEmpty())λ₯Ό ν†΅ν•˜μ—¬ Maze의 ν˜„μž¬ μœ„μΉ˜μ—μ„œ DC/DR을 ν†΅ν•œ nextPos의 값이 1μ΄κ±°λ‚˜ 0인 κ°’λ§Œ 이전 μœ„μΉ˜μ˜ κ°’ + 1을 ν†΅ν•˜μ—¬ κ±Έλ¦°μ‹œκ°„μ„ 계산해 μ£Όμ—ˆλ‹€.

이후 쀑간에 μžˆλŠ” ifλ¬Έμ—μ„œ Maze의 값이 end이면 int result에 값을 넣은후 break;λ₯Ό ν†΅ν•΄μ„œ 끝내렀고 ν–ˆλ‹€. ν•˜μ§€λ§Œ 그러자 κ°€μž₯ μ˜€λž˜κ±Έλ¦¬λŠ” λ―Έλ‘œνƒˆμΆœμ‹œκ°„μ΄ printλ˜μ—ˆλ‹€.
ν•˜μ§€λ§Œ break;λ₯Ό ν†΅ν•΄μ„œλŠ” λ°”κΉ₯의 whileλ¬Έ νƒˆμΆœμ΄ λΆˆκ°€λŠ₯ν•΄μ„œ, boolean flagλ₯Ό μ‚¬μš©ν•˜μ—¬ 검사해주렀닀가 κ²°κ΅­ return;을 ν†΅ν•˜μ—¬ ν”„λ‘œκ·Έλž¨μ„ λ°”λ‘œ λλ‚΄λŠ” λ°©μ‹μœΌλ‘œ κ΅¬ν˜„ν•˜μ˜€λ‹€.

ν•˜λ‚˜ν•˜λ‚˜μ”© μ—¬λŸ¬ μ•Œκ³ λ¦¬μ¦˜λ“€μ„ κ²©νŒŒν•΄κ°€λ©΄μ„œ μ‹€λ ₯이 뢀쩍 늘고 μžˆλŠ” λŠλ‚Œμ΄λΌμ„œ λ„ˆλ¬΄ ν–‰λ³΅ν•˜λ‹€.
λͺ©ν‘œκ°€ λ„ˆλ¬΄~~ 높은 것 κ°™μ§€λ§Œ, 내년이 였기 μ „κΉŒμ§€ 1000문제λ₯Ό ν‘ΈλŠ” 것이 λͺ©ν‘œμ΄λ‹€. 😎


πŸ“Œ Code

package BFS;

import java.io.*;
import java.util.*;

public class N2178 {
    static final int start = 1;
    static final int end = -2;
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] maze = new int[N][M];

        int num;

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                num = Character.getNumericValue(str.charAt(j));
                if (num == 0) {
                    maze[i][j] = -1;
                } else {
                    maze[i][j] = 0;
                }
            }
        }
        maze[0][0] = start;
        maze[N - 1][M - 1] = end;

        Queue<Integer[]> q = new LinkedList<>();
        q.add(new Integer[]{0, 0});
        Integer[] cur;
        int time;
        int nextRow;
        int nextCol;
        while (!q.isEmpty()) {
            cur = q.poll();
            time = maze[cur[0]][cur[1]] + 1;
            for (int i = 0; i < DC.length; i++) {
                nextRow = cur[0] + DR[i];
                nextCol = cur[1] + DC[i];
                if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M || maze[nextRow][nextCol] == -1) {
                    continue;
                }
                if (maze[nextRow][nextCol] == end) {
                    System.out.println(time);
                    return;
                }
                if (maze[nextRow][nextCol] == 0) {
                    q.add(new Integer[]{nextRow, nextCol});
                    maze[nextRow][nextCol] = time;
                }
            }
        }
    }
}

package (이름); λ₯Ό λ•Œκ³ , class 이름을 Main으둜 λ³€κ²½ν•˜λ©΄ λœλ‹€.



개인 곡뢀 기둝용 λΈ”λ‘œκ·Έμž…λ‹ˆλ‹€.
ν‹€λ¦¬κ±°λ‚˜ 였λ₯˜κ°€ μžˆμ„ 경우 μ œλ³΄ν•΄μ£Όμ‹œλ©΄ κ°μ‚¬ν•˜κ² μŠ΅λ‹ˆλ‹€.😁