[코드트리] 청약 챌린지 3회차 후기 BFS 공부해서 보완하기

🤓 BFS 공부하게 된 계기

 

갭체크를 응시했을 때 BFS를 부족한 지식으로 추천받아서 BFS를 이번주에 공부하게 되었다.

 

 

BFS에 대한 레슨으로는 이렇게 1, 2가 있었고, 이번주에는 Lesson 1을 끝내는 것을 목표로 잡았다!

 

✏️  BFS Lesson1. BFS 탐색 공부 후기

코드트리의 좋은 점은 아래 사진처럼 알고리즘에 대한 기본 개념을 알려준다는 점이다!

 

 

원래 이렇게 씨앗만 있던 상태에서 문제를 열심히 풀었고, 풀고 나면 아래 사진처럼 새싹🌱이 생겨나는 점이 코드트리의 귀여운 포인트인 것 같다! ㅎㅎ

하나 남은 씨앗은 Hard라서 아직 못 풀었다..

 

이번 Lesson1을 풀면서 막힌 문제는 'K번 최대값으로 이동하기' 문제였다.

간단하게 요약하자면,

N X N 격자판에서 한 시작점이 주어졌을 때, 현재 칸의 숫자보다 작은 칸들을 타고 이동하여 도달할 수 있는 전체 영역을 찾고, 그 영역 안에서 '가장 큰 숫자'가 있는 칸으로 이동하는 과정을 총 K번 반복하는 시뮬레이션 문제였다.
시뮬레이션 + BFS라서 조금 어렵게 느껴졌던 것 같다.

 

핵심 로직은
K번 움직일 때마다 bfs를 해서 갈 수 있는 칸을 모두 조사하면서 가장 큰 숫자가 있는 곳으로 이동했어야 했다.

 

그래서 아래와 같이 코드를 구현했다.

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


public class Main {

    static int N, K;
    static int[][] arr;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {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());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N][N];

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

        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken()) - 1;
        int c = Integer.parseInt(st.nextToken()) - 1;

        int answerX = r;
        int answerY = c;

        for (int step = 0; step < K; step++) {

            int[] nextPos = bfs(answerX, answerY);
            
            if (nextPos[0] == -1 && nextPos[1] == -1) {
                break;
            }
            
            answerX = nextPos[0];
            answerY = nextPos[1];
        }

        System.out.println((answerX + 1) + " " + (answerY + 1));

    }

    static int[] bfs(int startX, int startY) {
        int startVal = arr[startX][startY];

        Queue<int[]> queue = new LinkedList<>();
        int[][] visited = new int[N][N];

        queue.add(new int[] {startX, startY});
        visited[startX][startY] = 1;

        int bestX = -1;
        int bestY = -1;
        int bestVal = -1;

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curX = cur[0];
            int curY = cur[1];

            for (int d = 0; d < 4; d++) {
                int nX = curX + dx[d];
                int nY = curY + dy[d];

                if (!inRange(nX, nY))
                    continue;
                if (visited[nX][nY] == 1)
                    continue;
                if (arr[nX][nY] >= startVal)
                    continue;

                queue.add(new int[] {nX, nY});
                visited[nX][nY] = 1;

                if (arr[nX][nY] > bestVal) {
                    bestVal = arr[nX][nY];
                    bestX = nX;
                    bestY = nY;
                } else if (arr[nX][nY] == bestVal) { 
                    if (nX < bestX) {
                        bestX = nX;
                        bestY = nY;
                    } else if (nX == bestX) { 
                        if (nY < bestY) {
                            bestY = nY;
                        }
                    }
                }
            }
        }
        return new int[] {bestX, bestY};

    }

    static boolean inRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }
}

 

사실 bfs로 늘 최단거리 구할 때만 사용해봤지 Lesson1을 풀면서 다양한 유형의 문제를 bfs로 풀 수 있다는 점이 신기하면서도 유용했다!
bfs에 대해 조금은 더 알게 된 기분! 약점을 제대로 극복했는지는 갭체크를 통해서 다시 확인해보려고 한다.

 

🌲 코드트리의 좋은점

코드트리를 사용하면 갭체크로 약한 유형을 알 수 있고, 그 유형의 다양한 문제들을 풀어볼 수 있다는 점이 유용한 것 같다. BFS Lesson1 만 풀었음에도 다양한 유형을 볼 수 있었는데 Lesson2까지 풀면 bfs를 완전히 정복한 기분이 들지 않을까? 기대가 된다.

그리고 UI도 아기자기 귀엽게 되어 있어서 코딩을 하고 싶어지는 마음이 더 든다!!

 

https://www.codetree.ai/ko/trail-info

코딩 테스트 학습 안내 | 코드트리