[2024.11.06] BFS 탐색 / 우리는하나

 

오늘은 자소서 작성 등 여러 일들이 있어서 문제를 제대로 못 풀었음.

지금 너무 피곤해서 머리가 돌아가지 않는 관계로 내일 이어서 다시 풀어볼 예정

 

https://www.codetree.ai/missions/2/problems/we-are-the-one/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

난이도

• 중상
• 얘도 백트래킹 써줘야함(어떤 도시를 고를지 모든 경우의 수를 고려해줘야 하기 때문)

 

실수한 점 & 배운 점

•  

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

class Point{
    int r;
    int c;

    public Point(int r, int c){
        this.r = r;
        this.c = c;
    }

    public void setPoint(int r, int c){
        this.r = r;
        this.c = c;
    }
}

public class Main {
    static int n;
    static int k;
    static int u;
    static int d;
    static int[][] grid;
    static boolean[][] visited;
    static Queue<Point> queue;
    static Stack<Point> pickCity;

    static int[] dr = {1, 0, -1, 0};
    static int[] dc = {0, 1, 0, -1};

    public static void findCase(){
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                pickCity.push(new Point(i, j));
                findCase();
            }
        }
    }

    public static void findWay(){
        while(!queue.isEmpty()){
            Point curr = queue.poll();
            
            for(int i = 0; i<4; i++){
                int new_r = curr.r + dr[i];
                int new_c = curr.c + dc[i];
                if(canGo(new_r, new_c)){
                    if(tmpPoint==null) tmpPoint = new Point(new_r, new_c);
                    else if(isMax(new_r, new_c)) tmpPoint.setPoint(new_r, new_c);
                    
                    visited[new_r][new_c] = true;
                    queue.add(new Point(new_r, new_c));
                }
            }
        }
    }

    public static void findAllWay(){
        for(int i = 0; i<k; i++){
            visited[startPoint.r][startPoint.c] = true;
            queue.add(startPoint);
            findWay();
            if(tmpPoint!=null) startPoint.setPoint(tmpPoint.r, tmpPoint.c);
            init();
        }
    }

    public static boolean isRange(int r, int c){
        return (r>=0 && r<n && c>=0 && c<n);
    }

    public static boolean canGo(int r, int c){
        if(!isRange(r, c)) return false;
        if(grid[r][c]>=grid[startPoint.r][startPoint.c] || visited[r][c]) return false;
        return true;
    }

    public static boolean isMax(int r, int c){
        if(grid[r][c]>grid[tmpPoint.r][tmpPoint.c]) return true;
        else if(grid[r][c]==grid[tmpPoint.r][tmpPoint.c] && r<tmpPoint.r) return true;
        else if(grid[r][c]==grid[tmpPoint.r][tmpPoint.c] && r==tmpPoint.r && c<tmpPoint.c) return true;
        return false;
    }

    public static void init(){
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                visited[i][j] = false;
            }
        }
        tmpPoint = null;
    }

    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());
        u = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        grid = new int[n][n];
        visited = new boolean[n][n];
        queue = new LinkedList<>();
        pickCity = new Stack<>();

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