99클럽 코테 스터디 24일차 TIL - 그래프 (프로그래머스 '방의 개수')

항해99 코테 스터디 24일차 문제인 프로그래머스의 '방의 개수'는 원점을 기준으로 8개의 방향으로 이동하며 선을 긋고 최종적으로 생긴 방의 개수를 구하는 문제다. 난이도는 레벨5이며  오일러 지표를 통해 해결할 수 있다.

 

오늘의 문제 - 방의 개수 문제 정보

문제 키워드

- 그래프

난이도

- Level 5

 

문제 요약

• 원점 (0,0)에서 시작해 여덟 방향으로 이동하면서 선을 긋는다.
  • 0: ↑, 1: ↗, 2: →, 3: ↘, 4: ↓, 5: ↙, 6: ←, 7: ↖
  • 이미 그은 선을 다시 지나갈 수 있다.
  • 1 <= N <= 100,000
• 선긋기가 끝나고, 최종적으로 만들어진 방의 개수를 구하여라.
  • 방: 모든 곳이 막힌 다각형
  • 방 안에 다른 방이 만들어질 수 있다.

 

문제 풀이 과정  

 

[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0, 4, 1]일 때, 답은 4

 

1. 방의 개수를 어떻게 구할 것인가?
   • 예제 케이스를 보고 그림을 그려가며 생각해보니, 선을 긋다가 이미 지나온 점을 다시 만나면 무조건 방이 하나 생긴다는 것을 알게 되었다. 선을 계속 이어서 그리기 때문에 이미 방문했던 점이라면 무조건 다른 선과 이어져 있으므로, 다시 방문하게 되면 방이 하나 추가된다.
   • 그렇지만 이걸로 끝이면 레벨5일리가 없지! 선과 선이 교차되는 곳을 고려하는 것이 중요 포인트였다. →  그어진 선을 교차해서 지나간다면 방이 하나 더 생긴다. 사실 위의 경우와 같다. 선을 교차한다는 것은 교차점을 다시 방문한 것과 같으므로 방이 하나 추가되는 것이다. 물론 이 경우에도 도착한 점이 이미 방문했던 점이라면 방이 하나 더 추가된다. (그러므로 선 하나에 최대 2개 추가)
2. 먼저 생각한 방법은 평소에 그래프 탐색을 할 때처럼 방문 행렬을 만들고 그래프를 돌면서 무언가를 하는 방식이었다. 그러나 N이 10만까지 커지므로 가능한 좌표가 너무 커져서 방문 행렬을 만들 수 없다는 문제에 빠졌다.
   • 챗GPT한테 힌트를 얻어, 선을 모두 확인하여 선이 그어지는 좌표의 범위를 먼저 구해도 O(n)밖에 안 든다는 것을 깨달았다. → (0,0)을 시작으로 좌표의 최대값과 최소값을 구하여, 그려지는 전체 도형의 크기를 알 수 있다. 그렇게 전체 높이와 너비, 그리고 시작할 점의 좌표를 구하고 방문 표시 배열을 만들었다.
   • 또한 선의 중복도 확인해야 하므로, 각 점에서 그어진 선을 표시하는 size 8의 배열도 만들었다. 그랬더니 아니나 다를까 메모리 초과! 채점할 때 마지막 케이스 2개만 메모리 초과가 나고 나머지는 통과인 걸 보니, 풀이 자체는 맞은 것 같아서 메모리를 줄이기 위해 고민을 해보았다.
3. 메모리 줄이기
   • 아무래도 선을 체크하려고 만든 x8 배열이 너무 커지는 것 같았다. 어차피 모든 점에 모든 방향의 선이 그어지지는 않을 테니까 점을 방문할 때, 선을 저장하기 위한 set을 매핑해주도록 하였다. (Map<Point, Set<Integer>>, 여기서 Point는 record처럼 동작해야 함) 그리고 매 선(arrow)마다 아래 로직을 수행하였다. → 이렇게 Map으로 바꾸니 메모리까지 통과!
     1. 이미 그은 선인 경우 패스
     2. 이미 방문한 점인 경우 방 추가
     3. 선이 대각선이고 이미 그어진 다른 선과 교차되면 방 추가
     4. 방문 표시 및 선 저장
4. 자 이제 문제는 맞췄고, 코드를 정리해보자 싶어서 다시 보는데...
   • 잘 보니 visited 행렬을 따로 둘 필요 없이 Map에 저장하면 되겠다는 생각이 들었다. 그리고 더 생각해보니, Map에 좌표가 들어갔다는 것 자체로 이미 방문했다는 의미라는 걸 깨달았다! 그리고 더더 생각해보니, 내가 구한 원점도 높이도 너비도 필요가 없었다! → 바로 싸악 지우고, Set도 클래스화 해서 깔삼한 코드로 만들어서 다시 제출해서 통과!
5. 다 풀고나서 다른 사람들 해설을 보니, 내가 한 방식이 결국 "오일러의 다면체 정리"를 활용한 것이었다.
   • 2차원에서 → v - e + f = 1 (v: 점, e: 선, f: 면)
     • 오일러 정리 관련 글: https://suhak.tistory.com/189
   • 이 공식을 사용하면 아주 간단히 문제가 풀린다...! 물론 선이 교차되는 것을 고려해서, 점과 점 사이에 가운데 점을 추가해야 한다. (ex - (0.5, 0), (0, 0.5) 등도 존재)

내가 푼 코드

import java.util.*;

class Solution {
    
    private final int[][] drdc = {{1,1,0,-1,-1,-1,0,1}, {0,1,1,1,0,-1,-1,-1}};
    private final int[] opposite = {4,5,6,7,0,1,2,3};
    
    public int solution(int[] arrows) {
        int answer = 0;
        
        // 각 점에 연결된 선 정보를 저장할 Map
        // Map의 Key들 = 방문한 Point들
        Map<Point, Lines> lines = new HashMap<>();
        
        // 시작점 방문 표시
        Point now = new Point(0,0);
        lines.put(now, new Lines());
        
        for(int arrow: arrows) {
            // 선으로 이어진 다음 좌표
            Point next = now.getNext(arrow);
            
            // 현재 선이 이미 그은 선인 경우 좌표 정보만 갱신하고 넘어가기
            Lines nowLines = lines.get(now);
            if (nowLines.hasLine(arrow)) {
                now = next;
                continue;
            }
            
            // 이미 방문했던 좌표를 다시 방문하는 경우 도형 추가
            if (lines.containsKey(next)) {
                answer++;
            }
            
            // 대각선인 경우 (1,3,5,7) 
            if (arrow % 2 == 1) {
                // 이미 그어진 선과 교차되면 도형 추가
                Point cross = new Point(now.r, next.c);
                Lines crossLines = lines.get(cross);
                if (crossLines != null && crossLines.hasLine(8-arrow)) {
                    answer++;
                }
            } 
            
            // 기존 좌표에 새로운 선 정보 저장
            nowLines.addLine(arrow);
            
            // 다음 좌표 방문 표시 및 선 정보 저장
            Lines nextLines = lines.getOrDefault(next, new Lines());
            nextLines.addLine(opposite[arrow]);
            lines.put(next, nextLines);
            
            // 다음 좌표로 이동
            now = next;
        }
        
        return answer;
    }
    
    // 점에 연결된 선 정보를 저장할 클래스
    private class Lines {
        // 해당 점에 연결된 선의 방향
        private Set<Integer> directions = new HashSet<>(); 
        
        public Lines() { }
        
        public void addLine(int arrow) {
            directions.add(arrow);
        }
        
        public boolean hasLine(int arrow) {
            return directions.contains(arrow);
        }
    }
    
    // 객체가 아닌 데이터로서의 Point 클래스 정의
    private class Point {
        int r; int c;
        
        public Point (int r, int c) {
            this.r = r;
            this.c = c;
        }
        
        public Point getNext(int arrow) {
            return new Point(r + drdc[0][arrow], c + drdc[1][arrow]);
        }
        
        @Override
        public boolean equals(Object o) {
            if(this == o) return true;    
            if(o == null || this.getClass() != o.getClass()) return false;

            Point other = (Point) o;

            return other.r == this.r && other.c == this.c;
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(r, c);
        }
    }
}

• 시간복잡도: O(E)
• 공간복잡도: O(V)

 

오일러 공식 적용 코드

import java.util.*;

class Solution {
    
    private final double[][] drdc = {{0.5,0.5,0,-0.5,-0.5,-0.5,0,0.5}, {0,0.5,0.5,0.5,0,-0.5,-0.5,-0.5}};
    
    public int solution(int[] arrows) {
        int answer = 0;
        
        Set<Point> vertexs = new HashSet<>();
        Set<Line> edges = new HashSet<>();
        
        // 시작점 추가
        Point now = new Point(0, 0);
        vertexs.add(now);
        
        for(int a=0; a<arrows.length; a++) {
            int arrow = arrows[a];
            for (int i=0; i<2; i++) {
                Point next = now.getNext(arrow);
                vertexs.add(next);
                edges.add(new Line(now, next));
                now = next;
            }
        }
        
        return 1 - vertexs.size() + edges.size();
    }
    
    // s와 d가 반대여도 같은 Line이 되도록 equals와 hashCode 재정의
    private class Line {
        Point s;
        Point d;
        
        public Line (Point s, Point d) {
            this.s = s;
            this.d = d;
        }
        
        @Override
        public boolean equals(Object o) {
            if(this == o) return true;    
            if(o == null || this.getClass() != o.getClass()) return false;

            Line other = (Line) o;

            return (s.equals(other.s) && d.equals(other.d)) || (s.equals(other.d) && d.equals(other.s));
        }
        
        @Override
        public int hashCode() {
            return s.hashCode() >= d.hashCode() ? Objects.hash(s, d) : Objects.hash(d, s);
        }
    }
    
    // 좌표가 같으면 같은 Point가 되도록 equals와 hashCode 재정의
    private class Point {
        double r; double c;
        
        public Point (double r, double c) {
            this.r = r;
            this.c = c;
        }
        
        public Point getNext(int arrow) {
            return new Point(r + drdc[0][arrow], c + drdc[1][arrow]);
        }
        
        @Override
        public boolean equals(Object o) {
            if(this == o) return true;    
            if(o == null || this.getClass() != o.getClass()) return false;

            Point other = (Point) o;

            return other.r == this.r && other.c == this.c;
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(r, c);
        }
    }
}

 

오늘의 학습 회고

새롭게 알게된 것

• 오일러 공식...? 오일러 정리..? 암튼 진짜 오랜만에 보게 된 공식이다. 기억해두자!