BFS 풀어보고 claude code 한테 피드백 받기

 

BFS를 풀어보고 싶어서. 백준 알고리즘 사이트에서 

1261번

알고스팟 

문제를 가지고 풀어보고 클로드코드에게 피드백을 받아봤다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    /**
     *  N*M 미로
     *  운영진이 여러명이고 상하 좌우 이동이  -- 운영진이 여러명이지만 같이 이동하니까 하나의 객체라고 생각.
     *  벽은 이동할수 없지만 무기를 이용해서 없앨수 있음.
     *  무기가 몇개가 있는지 모르지만 사용해서 1,1 에 있는 운영진이 N,M에 갈때 필요한 무기의 개수
     *  N,M 입력값이 최대 값이 10^2 이라서 10^8 으로 일반적인 CPU 1초 기준 보다 매우 낮기 때문에 빅오 n2 도 무리 없을거 같다는 생각도 해봅니다.
     *  그리고 입력값들은 모두 0 또는 1임으로 Long 이아닌 int로도 충분하다는 생각도 미리 해봅니다.
     *  011
     *  111
     *  110
     *  입력값을 생각해보면, 문제에서 1,1 은 사실 0,0을 의미합니다 0,0은 항상 0이여야 한다는 것이고, N-1,M-1 을 구하는 문제 입니다.
     *  0,0 에서 N-1,M-1 로 갈때 최소 무기 개수.
     * 방향으로 가는건 사실 BFS 나 DFS 방식이 있는데요.  최소라는 단어가 있듯이 최단거리 최소를 구해야하기 때문에 bfs로 진행하빈다.
     *  이동을 하면서 가중치가 적용되니까 우선순위 큐를 통해서
     */
    static int[][] maze;
    static int[][] dist;
    static int[] dr = {0,0,-1,1};
    static int[] dc = {-1,1,0,0};
    static int M,N;
    public static void main(String[] args) throws IOException {
        inputMaking(); // 입력 구성완료
        bfsService(); // 실행.


    }

    private static int bfsService() {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(value -> value[0])); // 첫 요소에 가중치 넣기

        priorityQueue.offer(new int[]{0,0,0}); // 첫 시작은 0 가중치로 항상 0,0 에서 시작합니다.

        while (!priorityQueue.isEmpty()){
            int[] current = priorityQueue.poll();
            int curCost = current[0];
            int curRow = current[1];
            int curCol= current[2];

            if(curRow == N-1 && curCol == M-1){// 최종값 return
                return curCost;
            }

            for(int i = 0; i<4;i++){ // 상 하 좌 우 에 대해서 처리합니다.
                int nextRow = curRow + dr[i];
                int nextCol = curCol + dc[i];
                int nextCost = curCost + maze[nextRow][nextCol]; // 기존 가중치 + 현재 가중치.

                if(nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= M) continue;
                // 기존 가중치 보다 적을 때만 넣기 .
                if(nextCost < dist[nextRow][nextCol]){
                    dist[nextRow][nextCol] = nextCost;
                    priorityQueue.offer(new int[]{nextCost,nextRow,nextCol});
                }


            }
            // 우선순위로 넣게 되면 4방향 중에서 가중치가 작은 순서대로 값이 정렬 됩니다.


        }

        return -1; // 예외 처리.
    }

    private static void inputMaking() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        maze = new int[N][M];
        dist = new int[N][M];

        for(int i =0;i<N;i++){
            String input = bufferedReader.readLine();
            for(int j=0;j<M;j++){
                maze[i][j] = input.charAt(j)-'0';
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
    }


}

 

 

평소 머리속으로 시뮬레이션이 잘 안되서 시뮬레이션을 부탁했다.

 

시뮬레이션이라 많은 시뮬레이션을 해서 토큰이 많이 소진 되진  않을까 걱정도 있었지만, 적당한 시뮬레이션 예시를 들어주고

버그 까지 찾아주고 피드백 까지 주었다.

 

문제 자체를 당연히 잘 풀겠지만, 사고력을 기르려면, 스스로 풀어보고 피드백 받는게 우선이라 생각한다.