99클럽 코테 스터디 24일차 TIL: [프로그래머스] 방의 개수

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

프로그래머스

 

주의할 점은 다음과 같다.

• 방이 되기 위해선 다음 두 조건을 모두 만족해야 한다.
  • 이미 방문한 노드를 재방문 하는 경우
  • 해당 간선이 처음 생성된 간선인 경우
• 이차원 배열을 사용하려면 new int[200,001][200,001]의 크기의 배열이 필요하다. 따라서 이차원 배열을 사용할 수 없으며, 대신 Map을 사용한다. 
• 다음과 같이 교차점이 있을 경우 위 로직대로 생각하면, 방이 1개인 것으로 계산된다. 즉, 교차점까지 고려하기 위해선 다른 방법이 필요하다. 따라서 한 번의 이동을 2번의 이동으로 변경하면, 교차점이 있더라도 정상적으로 방이 2개인 것으로 계산된다.

• 참고로, 내가 생성한 Node라는 클래스에 대해 비교연산을 하기 위해선 equals 메소드와 hashCode 메소드를 재정의해줘야 한다.

import java.util.*;

class Solution {
    public int solution(int[] arrows) {
        
        int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
        int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
        int answer = 0;
        
        Map<Node, List<Node>> visited = new HashMap<>();
        Node now = new Node(0, 0);
        
        for (int arrow : arrows) {
            for (int i = 0; i < 2; i++) { // 2번 이동
                Node next = new Node(now.y + dy[arrow], now.x + dx[arrow]);
                
                // 처음 방문하는 경우
                if (!visited.containsKey(next)) {
                    visited.put(next, getList(now)); // key: next, value: now 추가
                    List<Node> list = visited.getOrDefault(now, new ArrayList<>());  // key: now, value: next 추가
                    list.add(next);
                    visited.put(now, list);
                } 
                
                // 재방문 + 처음 생성된 간선인 경우 -> 방 생성
                else if (visited.containsKey(next) && !visited.get(next).contains(now)) { 
                    visited.get(next).add(now); // key: next, value: now 추가
                    visited.get(now).add(next); // key: now, value: next 추가
                    answer++;
                }
                now = next;
            }
        }
    
        return answer;
    }
    
    private List<Node> getList(Node node) {
        List<Node> list = new ArrayList<>();
        list.add(node);
        return list;
    }
    
    private static class Node {
        
        int y, x;
        
        public Node (int y, int x) {
            this.y = y;
            this.x = x;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return x == node.x && y == node.y;
        }
 
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}