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

 

코딩테스트 연습 - 방의 개수

문제 설명

원점(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년 전에 파이썬으로 풀었던 문제였지만, 한번에 풀지 못했다. (심지어 똑같은 방법으로 틀린 접근을 시도했다.)

 

이전에 풀이와 아래 블로그를 참고하였다.

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

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

 

arrows를 통해 방이 형성되기 위해서는 이미 방문한 정점을 한번 더 방문해야 한다. 단, 2가지 부분에 대해 고려해야 한다.

 

1. 방을 중복해서 카운팅하거나, 단순 와리가리로 방문한 정점을 한번 더 방문하는 것에 대한 처리

이러한 경우를 체크하기 위해서 방문 여부를 들어오는 방향까지 고려하여 체크해야 한다. key로는 정점, value로는 해당 정점으로 들어오기 직전의 정점 리스트를 가지는 Map을 이용한다. 리스트에 이미 정점이 포함되어 있는 경우는 해당 방향으로 들어온 적이 있다는 것을 의미하므로 이 경우는 카운팅을 하지 않는다.

 

2. 정점이 없는 지점에서 교차하는 경우

예를 들어 (0, 0) -> (1, 1)의 직선과 (1, 0) -> (0, 1)의 직선이 있다고 생각해보자. 두 지점은 교차를 하게 되고, 이 경우에 4개의 방이 생길 여지가 있지만 교차점이 정점을 지나지 않기 때문에 카운팅되지 않는다. 이를 위해서 움직이는 단위를 한번에 한 칸이 아니라 두 칸씩 이동하도록 하면 정점이 없던 교차지점도 정점이 생긴다. (이 방식을 스케일 업이라고 하는 것 같다.)

 

+ Java에서 객체의 비교

객체를 비교할 때 별다른 처리를 하지 않으면 객체 간 비교는 객체의 참조값을 통해서 비교한다. 즉, 객체가 가진 값이 같더라도 참조가 다르면 다른 객체로 취급한다는 것이다. 앞서서 Map의 key 값으로 정점(Point) 객체를 가지도록 한다고 했는데, 이 경우에도 key값을 비교할 때 같은 정보를 가진 객체더라도 참조가 다르면 예상하는 조회가 불가능하다.

이를 해결하기 위해서는 좌표를 나타내는 Point 객체에 hashCode()와 equals()를 오버라이딩 하여 재정의하는 작업이 필요하다.

 

코드

import java.util.*;

public class Solution {

    private int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    private int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

    public int solution(int[] arrows) {
        int answer = 0;

        Map<Point, List<Point>> visited = new HashMap<>();
        Point now = new Point(0, 0);

        for (int arrow : arrows) {
            for (int i = 0; i < 2; i++) {
                Point next = new Point(now.x + dx[arrow], now.y + dy[arrow]);

                if (!visited.containsKey(next)) {
                    visited.put(next, makeDefaultList(now));

                    if (visited.get(now) == null) {
                       visited.put(now, makeDefaultList(next));
                    } else {
                        visited.get(now).add(next);
                    }
                } else if (visited.containsKey(next) && !visited.get(next).contains(now)) {
                    visited.get(next).add(now);
                    visited.get(now).add(next);

                    answer++;
                }

                now = next;
            }
        }

        return answer;
    }

    private List<Point> makeDefaultList(Point point) {
        List<Point> list = new ArrayList<>();
        list.add(point);

        return list;
    }

    class Point {
        int x;
        int y;

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

        @Override
        public int hashCode() {
            return Objects.hash(this.x, this.y);
        }

        @Override
        public boolean equals(Object obj) {
            Point point = (Point) obj;
            return this.x == point.x && this.y == point.y;
        }
    }
}