[소프티어] [HSAT 2회 정기 코딩 인증평가 기출] 사물인식 최소 면적 산출 프로그램(JAVA)

문제

https://softeer.ai/practice/6277

---

풀이(25분)

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

public class Main {
    static int n, k;
    static HashMap<Integer, List<Point>> dots = new HashMap<>();
    static int answer = Integer.MAX_VALUE;

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

        for (int i = 1; i <= k; i++) {
            dots.put(i, new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) + 1000;
            int y = Integer.parseInt(st.nextToken()) + 1000;
            int color = Integer.parseInt(st.nextToken());
            dots.get(color).add(new Point(x, y)); // 해당 색깔에 좌표 추가
        }

        // 탐색 순서를 최적화 (x + y 기준 정렬)
        for (int i = 1; i <= k; i++) {
            dots.get(i).sort(Comparator.comparingInt(p -> p.x + p.y));
        }

        // 1번 색깔의 모든 점을 시작점으로 DFS 호출
        for (Point p : dots.get(1)) {
            dfs(new DfsNode(p.x, p.y, p.x, p.y, 2));
        }

        System.out.println(answer);
    }

    static void dfs(DfsNode node) {
        // 현재 사각형 넓이가 이미 answer보다 크거나 같으면 탐색 중지 (백트래킹)
        int currentArea = (node.maxX - node.minX) * (node.maxY - node.minY);
        if (currentArea >= answer) return;

        // 모든 색을 선택했으면 최소 넓이 갱신
        if (node.color == k + 1) {
            answer = currentArea;
            return;
        }

        for (Point p : dots.get(node.color)) {
            int nextMinX = Math.min(node.minX, p.x);
            int nextMinY = Math.min(node.minY, p.y);
            int nextMaxX = Math.max(node.maxX, p.x);
            int nextMaxY = Math.max(node.maxY, p.y);

            // 다음 DFS 호출
            dfs(new DfsNode(nextMinX, nextMinY, nextMaxX, nextMaxY, node.color + 1));
        }
    }

    static class DfsNode {
        int minX, minY, maxX, maxY, color;

        public DfsNode(int minX, int minY, int maxX, int maxY, int color) {
            this.minX = minX;
            this.minY = minY;
            this.maxX = maxX;
            this.maxY = maxY;
            this.color = color;
        }
    }

    static class Point {
        int x, y;

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

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

public class Main {
    static int n, k;
    static HashMap<Integer, List<Point>> dots = new HashMap<>();
    static int answer = Integer.MAX_VALUE;
    static Set<DfsNode> visited = new HashSet<>(); // 방문한 상태 저장

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

        for (int i = 1; i <= k; i++) {
            dots.put(i, new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) + 1000;
            int y = Integer.parseInt(st.nextToken()) + 1000;
            int color = Integer.parseInt(st.nextToken());
            dots.get(color).add(new Point(x, y)); // 해당하는 색깔에 좌표 추가
        }

        for (Point p : dots.get(1)) {
            dfs(new DfsNode(p.x, p.y, p.x, p.y, 2));
        }

        System.out.println(answer);
    }

    static void dfs(DfsNode node) {
        if (node.color == k + 1) {
            answer = Math.min(answer, (node.maxX - node.minX) * (node.maxY - node.minY));
            return;
        }

        for (Point p : dots.get(node.color)) {
            int nextMinX = Math.min(node.minX, p.x);
            int nextMinY = Math.min(node.minY, p.y);
            int nextMaxX = Math.max(node.maxX, p.x);
            int nextMaxY = Math.max(node.maxY, p.y);
            DfsNode nextDfsNode = new DfsNode(nextMinX, nextMinY, nextMaxX, nextMaxY, node.color + 1);

            // 중복 상태라면 탐색하지 않음
            if (visited.contains(nextDfsNode)) {
                continue;
            }

            visited.add(nextDfsNode);
            dfs(nextDfsNode);
        }
    }

    static class DfsNode {
        int minX, minY, maxX, maxY, color;

        public DfsNode(int minX, int minY, int maxX, int maxY, int color) {
            this.minX = minX;
            this.minY = minY;
            this.maxX = maxX;
            this.maxY = maxY;
            this.color = color;
        }

        // equals 오버라이딩 (같은 상태인지 비교)
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            DfsNode dfsNode = (DfsNode) obj;
            return minX == dfsNode.minX &&
                   minY == dfsNode.minY &&
                   maxX == dfsNode.maxX &&
                   maxY == dfsNode.maxY &&
                   color == dfsNode.color;
        }

        // hashCode 오버라이딩 (Set에서 빠르게 비교)
        @Override
        public int hashCode() {
            return Objects.hash(minX, minY, maxX, maxY, color);
        }
    }

    static class Point {
        int x, y;

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

---

문제 풀이 전략

 

좌표를 기준으로 계산을 해야 한다. 하지만 좌표의 범위가 -1000~1000이기 때문에 일단 1000을 더해 인덱스를 사용하는 경우 편리하게 설정해 준다.(실제로 여기서 인덱스로 사용하지는 않는다.)

 

좌표는 2000x2000개가 존재하고, 이 중 2개를 뽑아 20개의 점이 모두 들어가는지 확인하려면 2000C2 * 20 정도의 계산이 필요하다. 이는 시간 초과가 발생하기 때문에 좌표를 기준으로 하는 것이 아닌 색깔을 기준으로 하는 것으로 변경했다.

 

1.

색깔을 기준으로 HashMap<Integer,List<Point>>를 통해 각 색깔별로 좌표를 기록한다.

이를 dfs를 통해 다음 색깔과 좌표를 기록해나간다.

이때 좌표는 좌하단과 우상단만 기록하며, dfs를 진행하는 모든 과정 속에서 넓이 체크를 진행하여 이미 넓이가 최소 넓이보다 크다면 바로 return을 해줌으로써 시간 초과를 방지한다.

 

2.

혹은 두 번째 코드와 동일하게 equals & hashCode를 오버라이딩 함으로써 동일한 상태에 대해 체크한 적이 있다면 넘어가는 식으로 시간 초과를 방지해도 된다.