프로그래머스 방의 개수 Java

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

프로그래머스

1. 문제 설명

원점(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

2. 시나리오

• arrows의 크기가 최대 10만이므로, 점을 배열에 표시할 수 없다.
  => O(1)로 방문 여부를 알기 위해 점을 HashSet을 사용하여 방문처리한다. 
• 각 점을 Node(x, y)로 표현한다.
  • 각 점을 비교하기 위해, equals() 함수를 Override한다.
  • 각 점을 해싱하여 Map과 Set에 저장하기 위해 hashCode()를 Override 한다.
• Map<Node, HashSet<Node>>로 방문표시한다.
  • 이미 방문한 점을 다시 방문한다면 방이 하나 만들어진 것이다.
    하지만 이미 방문한 점이라도 같은 방향이 아닌, 다른 방향에서 왔을 때 같은 점이어야 한다.
  • 예를 들어, 점 A에서 점 B를 방문한 적이 있을 때, 점 A가 아닌 다른 점에서 점 B를 방문해야 방이 만들어지는 것이다.
  • 즉, 다음으로 갈 점이 이미 방문한 점이고, 현재 점에서는 방문하지 않았다면 방이 만들어진다.
• Map에 양방향으로 방문 표시를 해준다.
  • 왜냐하면 A ->B 로 갔다가, 그다음 B -> A 라면 방이 만들어지지 않아야 하기 때문.
    ex) direction이 [0, 4]일 때
• 현재 점 cur를 next로 갱신한다.
• 대각선이 교차할 때도, 방이 하나 만들어지는데 이 경우는 교차하는 지점을 표시하지 않았기 때문에 count 되지 않는 반례가 있다. 그래서 크기를 2배로 늘린다.

 

3. 코드

import java.util.*;

class Solution {
    
    
    static Map<Node, HashSet<Node>> map = new HashMap<>();
    
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, 1, 1, 1, 0, -1 ,-1 ,-1};
    
    public int solution(int[] arrows) {
        int answer = 0;
    
        map.put(new Node(0, 0), new HashSet<>());
        
        Node cur = new Node(0, 0);
        
        
        
        for(int i = 0 ; i < arrows.length; i++) {
            
            int direction = arrows[i];
            
            for (int j = 0; j < 2; j++) {
                int x = cur.x + dx[direction];
                int y = cur.y + dy[direction];

                Node next = new Node (x, y); //다음으로 방문할 점

                if (!map.containsKey(next)) { 
                    //다음으로 방문할 점이, 아직 방문하지 않은 점이라면
                    map.put(next, new HashSet<>()); //key에 추가함으로서 방문 표시
                } else if (map.containsKey(next) && !map.get(cur).contains(next)) {
                    //다음으로 방문할 점이, 이미 방문했지만 현재 점에서는 방문하지 않았으면
                    answer++; //방이 만들어진다.
                } 

                map.get(cur).add(next); //현재 점에서 다음으로 방문할 점 방문 표시
                map.get(next).add(cur); //


                cur = next; 
            }
                     
        }
                
        
        return answer;
    }
    
    public class Node {
        public int x;
        public int y;

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

        @Override //HashSet과 HashMap에 저장하기 위해
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override //각 점을 비교하여 같은 점인지 확인하기 위해
        public boolean equals(Object o) {
            return this.x == ((Node) o).x && this.y == ((Node) o).y;
        }
    }
    
}