(C#) 방의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/49190

프로그래머스

풀고보니 Lv5였던 문제

 

풀이

 처음 문제를 보고 든 생각은 bfs? 하지만 인덱스의 범위가 불분명하고 심지어 음수가 될 수도 있어서 배열은 쓸 수 없다고 생각했다.

 문제를 살펴보니 주어진 그림은 항상 한붓그리기이고, 선을 그리다 다른 선을 만나면 방이 하나 생긴다는 것을 직감적으로 알게 되었다.

 이 점에 착안해서, arrow를 따라 선을 그리면서 새로 그린 선이 기존의 선과 만나는지 체크해주기로 했다.

 

 그러기 위해서 간선 목록 edges가 필요했다.

 edges는 HashSet 형식으로, T = ((int x, int y) u, (int x, int y) v), 즉 u(x, y)와 v(x, y)로 두 점을 표현하기로 했다.

 그러나 간선 목록만으로는 교차점이 생기는지 확인하는게 불편했으므로 정점의 목록 vertice또한 만들기로 했다.

 vertice도 HashSet 형식으로, T = (int x, int y) 형태로 표현하기로 했다.

 

 arrow를 처리하면서 해야 하는 작업은 두가지 인데, 첫번째는 새로 만든 간선이 진짜 새로 만든 간선인지 확인하는 것이다. 예를 들어 [ 2, 6, 2, 6 ]이라는 입력을 받게 되면 선은 좌우로 왔다갔다 하며 같은 간선을 총 4번 생성하게 된다. 이렇게 이미 생성된 간선을 다시 지나가는 경우는 무시하고 다음 arrow로 넘어가야 한다.

 두번째는 새로 만든 간선이 진짜 새로 만든 간선일 때, 이 간선이 기존의 간선과 교차점을 만드는지 확인하는 것이다. 만약 교차점이 생긴다면 방이 하나 생길 것이므로 answer에 1을 더해준다.

 

 두 번째 경우에도 두가지 경우의 수가 있었다. 첫번째는 간선의 끝점 v가 vertice에 있는 경우다. 이 경우는 확인이 쉽다.

 두번째 경우가 놓치기 쉬운 포인트이고, 실제로 나도 놓쳤던 부분이다. 간선을 대각선으로 형성할 수 있기 때문에 생기는 문제이다. 예를 들어 입력값이 [2, 5, 2, 7 ] 일 때, 간선은 아래 그림과 같이 생성된다.

 

이 때 빨간색 지점에 교차점이 생기게 되는데, 간선의 끝점만 확인한다면 이 부분을 놓치게 된다. 따라서 새로운 간선을 그렸을 때, 만약 그 간선이 대각 방향이라면 한번 더 확인 작업을 해줘야한다.

 

해쉬함수

 여기까지 했을 때 튜플을 사용하는 대신 간선과 정점을 표현하는 구조체를 직접 구현하기로 했다. 왜냐면 두 간선 e1((0, 0), (1, 0))과 e2((1, 0), (0, 0))은 실질적으로 같은 간선이지만 메모리 상에서는 서로 다른 간선으로 취급되어 edges에 중복으로 추가되는 문제가 있었기 때문이다. 이를 해결하기 위해 새로운 간선을 만들 때 u와 v를 비교해 더 작은 쪽을 앞으로 오도록 처리해주고 있었지만, 이럴바에는 구조체를 만들어서 처리하는게 낫겠다는 판단이었다.

 

 HashSet은 값을 등록할 때, GetHashCode()를 통해 생성된 해쉬값을 인덱스로 가진다. GetHashCode를 오버라이드 하지 않더라도 구조체는 해쉬값을 구하는 함수 System.ValueType.GetHashCode를 가진다. 그러나 이 함수는 reflection을 사용하기 때문에 느리다.

 Reflection에 대한 자세한 설명은 아래의 링크에 있다.

 

https://learn.microsoft.com/ko-kr/dotnet/csharp/advanced-topics/reflection-and-attributes/

특성 및 리플렉션 - C#

 

 그렇기 때문에 GetHashCode 함수를 오버라이드 해서 해쉬 성능을 높인다.

 System.HashCode.Combine(x, y)를 사용해서 간단하게 해쉬함수를 구현할 수 있었다.

struct Vertex
{
    public int x, y;
    public Vertex(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    
    // Vertex의 해쉬값을 생성해주는 함수
    public override int GetHashCode()
    {
        return System.HashCode.Combine(x, y);
    }
}

 이제 Vertex에 GetHashCode 함수를 오버라이드 했다. 마찬가지로 Edge에도 GetHashCode 함수를 오버라이드 해야한다.

struct Edge
{
    public Vertex u, v;
    public Edge(Vertex u, Vertex v)
    {
        this.u = u;
        this.v = v;
    }
    
    // Edge의 해쉬값을 생성해주는 함수
    public override int GetHashCode()
    {
        return System.HashCode.Combine(u.GetHashCode(), v.GetHashCode());
    }
}

 그런데 여기서 또 하나 문제가 발생한다.

 System.HashCode.Combine은 교환법칙이 성립하지 않는듯하다. 즉, Combine(u, v)와 Combine(v, u)의 값이 다르다는 것이다.

 이렇게 되면 Edgs(u, v)와 Edge(v, u)가 서로 다른 간선으로 취급되어 중복 추가되는 문제가 발생한다.

 

 따라서 안타깝게도 u와 v를 비교해서 오름차순으로 할당하기로 했다.

 이를 위해 Vertex에 CompareTo함수를 구현해준다.

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

    public override int GetHashCode()
    {
        return System.HashCode.Combine(x, y);
    }

    // Vertex의 대소를 비교해주는 함수
    public int CompareTo(Vertex other)
    {
        if (this.x.CompareTo(other.x) < 0 || (x.CompareTo(other.x) == 0 && y.CompareTo(other.y) < 0))
            return -1;
        else if (x.CompareTo(other.x) == 0 && y.CompareTo(other.y) == 0)
            return 0;
        else
            return 1;
    }
}

 

 이제 Edge의 생성자에서 입력받은 두 Vertex u, v를 비교함으로써 GetHashCode의 일관성을 확보하게 되었다.

struct Edge
{
    public Vertex u, v;
    public Edge(Vertex u, Vertex v)
    {
        // u와 v중에 누가 더 큰지 비교해서 오름차순으로 할당한다
        if (u.CompareTo(v) < 0)
        {
            this.u = u;
            this.v = v;
        }
        else
        {
            this.u = v;
            this.v = u;
        }
    }
    
    public override int GetHashCode()
    {
        return System.HashCode.Combine(u.GetHashCode(), v.GetHashCode());
    }
}

 

 Edge와 Vertex 구조체를 구현했으니 다시 본문으로 돌아가서, 각 arrow에서 세가지를 확인해야한다.

 첫번째, 이번 arrow가 새로운 간선을 만드는지 확인한다.

 두번째, arrow의 끝에 기존 edge가 있는지 확인한다.

 세번째, arrow가 다른 대각선 edge과 교차하는지 확인한다.

 

 첫번째는 간단하다. HashSet.Add 함수는 값을 성공적으로 추가했을 때 true를 반환한다. 만약 edges.Add(arrow)가 true라면 새로운 간선이다.

 두번째도 간단하다. 마찬가지로 vertice.Add(v)가 true라면 새로운 정점이다.

 세번째는 조금 다르다. 먼저 이번 arrow가 대각선인지 확인해야한다. arrow의 시작점이 (x, y), 끝점이 (_x, _y)라고 할 때, x != _x && y != _y라면 arrow는 대각선이다.

 그 다음은 arrow가 다른 간선과 교차하는지 확인해야한다. 즉, arrow와 교차하는 간선이 이미 edge에 있는지 확인한다.

 arrow와 교차하는 간선 cross는 (x, _y), (_x, y)로 표현할 수 있다. x와 _x의 대소관계는 상관없다. 어차피 Edge 생성자에서 검사해주기 때문이다. 따라서 var cross = new Edge(new Vertex(x, _y), new Vertex(_x, y))로 생성해주고, edges.Contains(cross)를 검사해주면 된다.

 

 두번째와 세번째는 완전히 독립적이므로, 두 경우에 해당할때마다 answer에 1을 더해주면 원하는 답을 구할 수 있다.

 

코드

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] arrows) {
        int answer = 0;
        int x = 0, y = 0;
        int[] dx = new int[] { 0, 1, 1, 1, 0, -1, -1, -1 };
        int[] dy = new int[] { 1, 1, 0, -1, -1, -1, 0, 1 };

        HashSet<Edge> edges = new HashSet<Edge>(100000);
        HashSet<Vertex> vertice = new HashSet<Vertex>(100000);

        for (var i = 0; i < arrows.Length; i++)
        {
            var _x = x + dx[arrows[i]];
            var _y = y + dy[arrows[i]];
            var u = new Vertex(x, y);
            var v = new Vertex(_x, _y);
            var edge = new Edge(u, v);
            vertice.Add(u);
            var newVertex = vertice.Add(v);
            var newEdge = edges.Add(edge);
            if (newEdge)
            {
                if (!newVertex)
                    answer++;
                if (x != _x && y != _y)
                {
                    var cross = new Edge(new Vertex(x, _y), new Vertex(_x, y));
                    if (edges.Contains(cross))
                        answer++;
                }
            }
            x = _x;
            y = _y;
        }
        return answer;
    }

    struct Edge
    {
        public Vertex u, v;
        public Edge(Vertex u, Vertex v)
        {
            if (u.CompareTo(v) < 0)
            {
                this.u = u;
                this.v = v;
            }
            else
            {
                this.u = v;
                this.v = u;
            }
        }
        
        public override int GetHashCode()
        {
            return System.HashCode.Combine(u.GetHashCode(), v.GetHashCode());
        }
    }

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

        public override int GetHashCode()
        {
            return System.HashCode.Combine(x, y);
        }

        public int CompareTo(Vertex other)
        {
            if (this.x.CompareTo(other.x) < 0 || (x.CompareTo(other.x) == 0 && y.CompareTo(other.y) < 0))
                return -1;
            else if (x.CompareTo(other.x) == 0 && y.CompareTo(other.y) == 0)
                return 0;
            else
                return 1;
        }
    }
}

 

후기

 효율적인 해쉬함수가 얼마나 중요한지 알게 되었다. Vertex가 기본 해쉬함수인 System.ValueType.GetHashCode를 사용할 때와 직접 구현한 해쉬 함수를 사용할 때 극명한 성능 차이가 있었다. 어느정도냐면, 기본 해쉬함수를 사용할때는 시간초과가 발생하던 케이스가 직접 해쉬 함수를 구현해 주었을때는 약 100ms 수준까지 줄었다. 일반적으로 10초가 넘으면 시간초과가 뜬다는걸 감안했을 때, 최소 100배 이상의 차이가 발생한 것이다.

 그리고 중간에 튜플 대신 구조체로 설계를 바꿨는데, 만약 튜플을 계속 사용했다면 어떻게 해쉬함수를 만들 수 있을지 궁금해졌다.

 올해 초에 javascript를 공부하면서 튜플에 중독되었는데, 저번에 튜플 스왑 버그도 그렇고, 아직 프로그래머스 문제에서 튜플을 마음놓고 쓰기에는 어려운것같다.