[Week31] 스터디 회고

평일에 스케줄이 가득해서 멘토링과 과제 그리고 운동만으로도 알고리즘 문제 풀이 시간을 별도로 만들기 쉽지 않아서 주말에 몰아서 문제를 풀었다.

 

문제를 몰아서 풀다보니 코드 리뷰를 할 시간이 많이 부족해지고, 한 문제에 시간을 오래 소모하면 다른 문제에 시간을 많이 할당 못하기 때문에 부담이 되는 것 같다.

 

이번에 출제된 문제

• [G2] 인간 대포 (백준)
• [G5] 치킨 배달 (백준)
• [LV2] 멀쩡한 사각형 (프로그래머스)

---

[ 📌 내 문제 풀이 with Java ]

👉 인간 대포

 

다익스트라 알고리즘을 이용해서 문제를 풀이 하였는데, 코드를 살펴보면 다익스트라 로직 자체는 정말 심플하다.

나는 계산기로 수소점 계산하면서 문제가 생기는 부분을 디버깅 하는 시간을 많이 사용했다.

 

문제를 풀이 하다가 문제가 되었던 부분

1. 처음 시작 위치에서는 대포가 없기 때문에 다음 대포까지 걸어서 이동 해야한다.
2. 대포가 한 개도 주어지지 않는 케이스에는 시작점에서 도착점까지 걸어서 이동 해야한다.

주어진 조건에 맞게 구현 한다면 크게 어렵지 않으나 하나라도 빼먹고 찾지 못하는 경우가 되면 정말 힘들어지는 문제...

덕분에 나는 힘들어져서 숨겨진 테스트 케이스를 아래에서 찾아서 알게 되었다.

https://cs.baylor.edu/~hamerly/icpc/qualifier_2014/

2014 ACM-ICPC North America Qualification Contest

 

/**
 * Author    : Lee In Bok
 * Date      : 2025.01.18(Sat)
 * Runtime   : 128 ms
 * Memory    : 14576 KB
 * Algorithm : Dijkstra
 * Ref       : https://cs.baylor.edu/~hamerly/icpc/qualifier_2014/
 */

package com.year2025.Week31;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class G2_10473 {

    // 각 노드 까지의 최소 시간 배열
    public static double[] times;
    public static List<Node> graph = new ArrayList();
    public static Queue<Node> pq = new PriorityQueue<>(Node::compareTo);

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        double srtX = Double.parseDouble(st.nextToken());
        double srtY = Double.parseDouble(st.nextToken());
        st = new StringTokenizer(br.readLine());
        double endX = Double.parseDouble(st.nextToken());
        double endY = Double.parseDouble(st.nextToken());
        int n = Integer.parseInt(br.readLine());

        times = new double[n + 2];
        Arrays.fill(times, Double.MAX_VALUE);

        for(int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());

            // 모든 노드 리스트에 저장
            graph.add(new Node(i, x, y, 0));
        }

        Node srtNode = new Node(0, srtX, srtY, 0);

        // 도착점 노드 리스트에 저장
        graph.add(new Node(n + 1, endX, endY, 0));

        // 시작 위치에는 대포가 없기 때문에 다음 대포 까지는 걸어서 이동 해야함
        for(Node node : graph) {
            double time = srtNode.getTimeFromStartByWalking(node);

            pq.add(new Node(node.nodeNo, node.x, node.y, time));
            times[node.nodeNo] = time;
        }

        dijkstra();

        System.out.println(times[n + 1]);
    }

    public static void dijkstra() {
        while(!pq.isEmpty()) {
            Node curNode = pq.poll();

            for(Node adjNode: graph) {
                if(curNode.equals(adjNode)) {
                    continue;
                }

                double time = curNode.getTimeMovingBetweenTwoNode(adjNode) + curNode.time;

                if(times[adjNode.nodeNo] > time) {
                    pq.add(new Node(adjNode.nodeNo, adjNode.x, adjNode.y, time));
                    times[adjNode.nodeNo] = time;
                }
            }
        }
    }

    static class Node implements Comparable<Node> {
        final double walkSpeed = 5.0;
        final double cannonDist = 50.0;
        final double cannonSpeed = 2.0;

        int nodeNo;
        double x;
        double y;
        double time;

        public Node(int nodeNo, double x, double y, double time) {
            this.nodeNo = nodeNo;
            this.x = x;
            this.y = y;
            this.time = time;
        }

        public double getWalkingTime(double dist) {
            return dist / walkSpeed;
        }

        public double getTimeFromStartByWalking(Node node) {
            return getWalkingTime(getDist(node));
        }

        public double getDist(Node node) {
            return Math.sqrt((x - node.x) * (x - node.x) + (y - node.y) * (y - node.y));
        }

        public double getTimeMovingBetweenTwoNode(Node node) {
            double dist = getDist(node);
            double walkTime = getWalkingTime(dist);
            double cannonTime = 2 + Math.abs(dist - cannonDist) / walkSpeed;

            return Math.min(walkTime, cannonTime);
        }

        @Override
        public int compareTo(Node o) {
            return Double.compare(this.time, o.time);
        }

        @Override
        public boolean equals(Object o) {
            Node n = (Node) o;

            return x == n.x && y == n.y;
        }
    }
}

---

👉 치킨 배달

 

치킨 집과 일반 집을 분리하기 위해서 class 를 나눠서 작성 했는데 지금 생각 해보니 아래와 같이 작성 했으면 더 깔끔 했을 것 같다.

static class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

static class Store extends Point {
    int dist;

    public Store(int x, int y) {
        super(x, y);
        this.dist = 0;
    }
}

static class House extends Point{
    int min;

    public House(int x, int y) {
        super(x, y);
        this.min = Integer.MAX_VALUE;
    }

    public int getMin() {
        return min;
    }

    public void setMin() {
        this.min = Integer.MAX_VALUE;
    }
}

 

어찌 되었든 알고리즘 문제 풀이에서 가장 중요한건 문제를 풀었냐이기 때문에 일단은 성공이라고 말하고 싶다.

백트래킹 기법을 이용해서 조합들을 만들어서 폐업 시켜야 할 치킨 구했다.

 

/**
 * Author    : Lee In Bok
 * Date      : 2025.01.19(Sun)
 * Runtime   : 296 ms
 * Memory    : 25976 KB
 * Algorithm : Backtracking
 */

package com.year2025.Week31;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class G5_15686 {

    public static int N;
    public static int M;
    public static int[][] map;
    public static Store[] comb;
    public static List<Store> storeList;
    public static List<House> houseList;
    public static boolean[] visited;
    public static int ans = Integer.MAX_VALUE;

    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());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        comb = new Store[M];

        storeList = new ArrayList<>();
        houseList = new ArrayList<>();

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < N; j++){
                int type = Integer.parseInt(st.nextToken());

                if(type == 1){
                    houseList.add(new House(i, j));
                } else if(type == 2){
                    storeList.add(new Store(i, j));
                }
            }
        }

        visited = new boolean[storeList.size()];
        backTracking(0, 0);

        System.out.println(ans);
    }

    public static void backTracking(int storeIdx, int comIdx){
        if(comIdx == M){
            int sum = 0;

            for(Store s : comb){
                for(int i = 0; i < houseList.size(); i++){
                    House h = houseList.get(i);
                    int dist = Math.abs(s.x - h.x) + Math.abs(s.y - h.y);

                    if(h.min > dist){
                        h.min = dist;
                    }
                }
            }

            for(int idx = 0; idx < houseList.size(); idx++){
                sum += houseList.get(idx).min;
            }

            sum = houseList.stream()
                           .map(House::getMin)
                           .mapToInt(Integer::intValue)
                           .sum();

            if(ans > sum){
                ans = sum;
            }

            houseList.forEach(House::setMin);

            return;
        }

        for(int i = storeIdx; i < storeList.size(); i++){
            if(!visited[i]){
                visited[i] = true;
                comb[comIdx] = storeList.get(i);
                backTracking(i + 1, comIdx + 1);
                visited[i] = false;
            }
        }
    }

    static class Store {
        int x;
        int y;
        int dist;

        public Store(int x, int y) {
            this.x = x;
            this.y = y;
            this.dist = 0;
        }
    }

    static class House {
        int x;
        int y;
        int min;

        public House(int x, int y) {
            this.x = x;
            this.y = y;
            this.min = Integer.MAX_VALUE;
        }

        public int getMin() {
            return min;
        }

        public void setMin() {
            this.min = Integer.MAX_VALUE;
        }
    }
}

---

👉 멀쩡한 사격형

 

사실 이 문제는 중복되서 출제된 문제인데 Week06 과 Week31 에 출제 되었고, 나는 두 번다 풀지 않았다...

문제를 못 풀어서 다른 풀이를 참고 했었고, 수학과 관련된 풀이들이 주되었기 때문에 나는 solved 까지는 포기 했다.

 

수학과 관련된 문제들과 마주치면 정말 힘든 것 같다... (접근도 힘들다..)

---

[📌 아쉬운 점...]

본래라면 못 푸는 문제도 풀이를 참고하고, 어떻게든 풀고 이해하는게 맞지만 요즘 스케줄에 치여서 포기가 빨라진 것 같다.

 

코드 리뷰또한 하지 못해서 많이 아쉬운데 이제 내가 게을러져서 하지 않을 핑계를 만드는건지 진짜 바쁜건지 의심하는 구간에 도달해 버렸다.

시간을 더 내면 낼 수 있을 것 같은데, 몸은 힘들고... 욕심 때문에 손에서 놓지 못해서 새로운걸 손에 집지 못하는건지...