99클럽 코테 스터디 8일차 TIL [BFS]

 

- 오늘의 학습 키워드 : BFS 알고리즘

 

[문제 이름 : 녹색 옷 입은 애가 젤다지? (백준 4485, G4)]
문제 url : https://www.acmicpc.net/problem/4485

내가 작성한 코드는 아래와 같다.

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

public class Main {

    static int n;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int index = 0;
        while(true) {
            n = Integer.parseInt(br.readLine());
            if(n==0) break;

            map = new int[n][n];
            visited = new boolean[n][n];

            for(int i=0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j=0; j<n; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            sb.append("Problem ").append(++index).append(": ").append(BFS()).append("\n");
        }


        System.out.println(sb.toString());
    }

    static int BFS() {
        PriorityQueue<Loopy> queue = new PriorityQueue<>();
        queue.add(new Loopy(0,0,map[0][0]));
        visited[0][0] = true;

        while(!queue.isEmpty()) {
            Loopy temp = queue.poll();
            if(temp.x == n-1 && temp.y == n-1) {
                return temp.value;
            }
            for(int i=0; i<4; i++) {
                int nx = dx[i] + temp.x;
                int ny = dy[i] + temp.y;

                if(nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new Loopy(nx,ny,temp.value + map[nx][ny]));
                }
            }
        }

        return -1;
    }

    static class Loopy implements Comparable<Loopy> {
        int x;
        int y;
        int value;

        Loopy(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }

        @Override
        public int compareTo(Loopy l) {
            return this.value - l.value;
        }
    }
}

 

풀이 과정 (풀이 시간 : 20분)

1. 0 입력 전까지, 반복해서 테스트 케이스를 입력받으므로 index 변수와 StringBuilder를 사용해 출력을 해주었다.

2. int[][] map에 도둑루피의 값을 저장하고, boolean[][] visited를 통해 방문 여부를 저장한다.
3. 최소값을 구해야 하므로, 좌표 x, y와 도둑 루피의 값을 저장하는 Loopy 클래스를 만들어준 후, PriorityQueue를 사용해서 값이 작은 것 먼저 Queue에 정렬될 수 있도록 구현한다.

4. 상하좌우로 이동할 수 있으므로, BFS를 돌리면서 배열 내에 있는 x,y 좌표이고, 아직 방문하지 않은 좌표라면 Queue에 추가한다. 이때, value는 현재 값에서 이동할 좌표의 루피 값을 더한다.

5. x == n-1, y == n-1 은 배열의 맨 오른쪽 아래에 도달한 것이므로, BFS 문을 종료한다.

내일은 공준생 유튜브를 참고하여 면접 예상 질문을 정리해볼 예정이다.

99클럽, Til, 개발자취업, 코딩테스트준비, 항해99