[프로그래머스] 방의 개수

문제

---

원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다.

ex) 1일때는 오른쪽 위로 이동

그림을 그릴 때, 사방이 막히면 방하나로 샙니다.
이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요.

 

 

[제한사항]

• 배열 arrows의 크기는 1 이상 100,000 이하 입니다.
• arrows의 원소는 0 이상 7 이하 입니다.
• 방은 다른 방으로 둘러 싸여질 수 있습니다.

 

 

 

[입출력 예]

arrows	return
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]	3

입출력 예 설명

• (0,0) 부터 시작해서 6(왼쪽) 으로 3번 이동합니다. 그 이후 주어진 arrows 를 따라 그립니다.
• 삼각형 (1), 큰 사각형(1), 평행사변형(1) = 3

 

 

풀이

---

방이 만들어지는 조건은 두가지다.

1. 한번 지나간 점으로 다시 돌아온 경우( 단 같은 간선을 반복하는 경우는 제외)
2.  X 모양으로 간선이 cross 되는 경우

반복문으로 하나씩 모두 확인할경우 시간초과가 발생하므로 HashSet을 구현하여 하였다.

 

그래프 문제지만 HashSet을 구현할 줄 알아야 한다.

기존의 int String 과 같은 경우는 이미 HashSet에서 구현이 되어있지만, 새로운 클래스는 HashSet을 구현할 줄 알아야한다.

 

 

HashSet을 구현하기 위해서는 @Override로 equals 와 hashCode 메소드가 있어야한다.

 

<@Override equals(Object) 메소드 예시>

@Override
public boolean equals(Object object){
    Point p = (Point) object;

    if(this.x == p.x && this.y == p.y) {return true;}

    return false;
}

위와 같이 Object를 인자로 받을 수 있고 새로 추가할 object가 이미 Set에 들어있는지 판단하는 역할을 한다.

하지만 이것만 추가해서는 HashSet의 add를 막을 수 없다. 이를 막기위해서 hashCode 메소드를 구현해야한다.

 

<@Override hashCode() 메소드 예시>

@Override
public int hashCode(){
    int prime = 31;
    int hashcode = 1;

    hashcode = prime * hashcode + this.x;
    hashcode = prime * hashcode + this.y;

    return hashcode;

}

여기서 hashcode가 같다면 hashSet에 추가하지 않게 하는 것이다. 

prime 을 31로 두는 이유는 31은 소수이면서 홀수이기 때문에 선택한 값이다. 만일 그 값이 짝수고 곱셈 결과가 오버플로 되었다면 해당 정보가 사라지기 떄문이다. 전통적으로 31을 두고 있지만 더욱 효율적인 수가 있다면 바뀔 수 있다.

 

두개의 @Override를 구현해야한다는 것을 알고 Point, Edge 클래스를 선언했다.

static class Edge{
    int x1, x2, y1, y2, d;

    Edge(int x1, int y1, int x2, int y2, int d){
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        this.d = d;            
    }

    @Override
    public boolean equals(Object object){
        Edge e = (Edge)object;

        if((Math.abs(this.d - e.d) == 4 || this.d == e.d) && (this.x1 + this.x2 == e.x1 + e.x2) && (this.y1 + this.y2 == e.y1 + e.y2)) {return true;}

        return false;
    }

    @Override
    public int hashCode(){
        int prime = 31;
        int hashcode = 1;
        int dir = this.d;

        if(this.d < 4) {dir += 4;}

        hashcode = prime * hashcode + (this.x1 + this.x2);
        hashcode = prime * hashcode + (this.y1 + this.y2);
        hashcode = prime * hashcode + dir;

        return hashcode;
    }
}

static class Point{
    int x, y;

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

    @Override
    public boolean equals(Object object){
        Point p = (Point) object;

        if(this.x == p.x && this.y == p.y) {return true;}

        return false;
    }

    @Override
    public int hashCode(){
        int prime = 31;
        int hashcode = 1;

        hashcode = prime * hashcode + this.x;
        hashcode = prime * hashcode + this.y;

        return hashcode;

    }
}

Point 클래스는 같은 점만 골라주면 되므로 크게 이해하는데 어려움이 없을 것이다.

 

하지만 Edge 클래스와 같은 경우는 방향이 반대인 간선을 찾아줘야 하기 때문에 x1+x2 y1+y2 가 모두 같은 경우에서 방향이 같거나 반대인 경우를 찾아 주었다.

 

hashCode() 메소드에서는 방향을 4보다 작으면 4를 더해 한가지 방향으로만 통일 시키는 방식을 이용하여 구현하였다.

 

이렇게 구현한 클래스를 이용하여 한번 지난 점으로 다시 돌아오는지, 대각선 방향으로 있는 간선을 지나쳐 가는지를 판단해주면 된다.

 

 

<전체코드>

import java.util.*;

class Solution {
    
    static class Edge{
        int x1, x2, y1, y2, d;

        Edge(int x1, int y1, int x2, int y2, int d){
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
            this.d = d;            
        }

        @Override
        public boolean equals(Object object){
            Edge e = (Edge)object;

            if((Math.abs(this.d - e.d) == 4 || this.d == e.d) && (this.x1 + this.x2 == e.x1 + e.x2) && (this.y1 + this.y2 == e.y1 + e.y2)) {return true;}

            return false;
        }

        @Override
        public int hashCode(){
            int prime = 31;
            int hashcode = 1;
            int dir = this.d;

            if(this.d < 4) {dir += 4;}

            hashcode = prime * hashcode + (this.x1 + this.x2);
            hashcode = prime * hashcode + (this.y1 + this.y2);
            hashcode = prime * hashcode + dir;

            return hashcode;
        }
    }

    static class Point{
        int x, y;

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

        @Override
        public boolean equals(Object object){
            Point p = (Point) object;

            if(this.x == p.x && this.y == p.y) {return true;}

            return false;
        }

        @Override
        public int hashCode(){
            int prime = 31;
            int hashcode = 1;

            hashcode = prime * hashcode + this.x;
            hashcode = prime * hashcode + this.y;

            return hashcode;

        }
    }
    
    
    static int[][] move = new int[][]{{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
    public int solution(int[] arrows) {
        int answer = 0;
        
        HashSet<Point> points = new HashSet<>();
        HashSet<Edge> edges = new HashSet<>();
        
        int x = 0;
        int y = 0;
        points.add(new Point(x, y));
        
        for(int i = 0 ; i < arrows.length ; i++){
            int dir = arrows[i];
            x += move[dir][0];
            y += move[dir][1];
            
            Point nowPoint = new Point(x, y);
            Edge nowEdge = new Edge(x - move[dir][0], y - move[dir][1], x, y, dir);
            //이미 있는 간선을 다시 돌아왔다면 간선을 추가 및 방의 개수를 판단하지 않고 continue를 해준다.
            if(edges.contains(nowEdge)) { continue; }
            
            //이미 있는 점에 다시 돌아왔는지 판단한다.
            if(points.contains(nowPoint)){
                answer++;
            }else{
                points.add(nowPoint);
            }
            
            //방향이 대각선 방향이면 cross 간선이 존재하는지 판단한다.
            Edge cross = new Edge(x - move[dir][0], y, x, y - move[dir][1], ((dir + 2) % 8));   
            if(dir % 2 == 1 && edges.contains(cross)){
                answer++;
            }
            
            edges.add(nowEdge);
        }
        
        return answer;
    }   
}