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

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

 

풀이과정

우선 방이 생성되는 조건에 대해 파악해야 합니다.

 

방이 생성되는 조건은

1. 이전에 방문했던 정점을 다시 방문해야 함

2. 이전에 연결한 선분이 아닌 새로 생긴 선분이어야 함

 

각 정점에 대한 그래프를 코드로 나타내는 과정이 중요하다고 생각합니다.

이때, 기존의 그래프 문제와 다르게 인접행렬이나 인접리스트로는 해당 문제를 구현할 수 없습니다.

arrows의 크기가 1 이상 100,000이하라는 조건으로 인해 인접 행렬의 경우200_001 * 200_001 의 크기가 되기 때문입니다.

 

아래와 같이 HashMap 자료구조와 Node 클래스를 통해서 그래프를 구현할 수 있습니다.

class Node{
    int r,c;
    
    public Node(int r,int c){
        this.r = r;
        this.c = c;
    }
    
    @Override
    public boolean equals(Object o){
        if(this==o) return true;
        if(o==null || !(o instanceof Node)) return false;
        Node node = (Node)o;
        if(node.r==this.r && node.c==this.c) return true;
        
        return false;
    }
    
    @Override
    public int hashCode(){
        final int prime = 31;
        int result = 1;
        result = result*prime + r;
        result = result*prime + c;
        return result;
    }
}

HashMap<Node,List<Node>> map = new HashMap();

 

HashMap의 키 값을 기준으로 방문한 정점이 이미 방문한 정점인지 파악이 가능하며,

value 값을 바탕으로 해당 선분이 이미 연결된 선분인지 파악이 가능합니다. (이때 ArrayList자료구조의 contains 메서드를 사용합니다.)

 

3. 대각선 선분이 교차하는 경우에 대해서도 고려해야 합니다.

대각선으로 선분이 교차하게 되면, 기존 로직에서 1개의 방이 생성되는 것으로 파악되지만 실제로는 2개의 방이 생성됩니다. 

이를 위해서 한 번의 이동을 2번의 이동으로 표현하면 교차 경우에 대한 문제를 해결할 수 있습니다.

for(int a : arrows){
	for(int i=0;i<2;i++){
    	// Node를 활용하여 정점을 탐색하고, 선분을 이으며 방이 생기는지 확인하는 로직
    }
}

 

 

 

알게된점

• 각 좌표(r,c) 에 대한 노드 번호를 나타내는데 어려움을 겪었습니다. Node 클래스를 사용해서 객체를 생성하여 노드를 나타낼 수 있음을 알게되었습니다.
• ArrayList 자료구조의 contains 메서드는 O(n)의 시간복잡도를 가지고, HashMap 자료구조의 contains 메서드는 O(1)의 시간복잡도를 가진다는 것을 알게되었습니다.
• equals 메서드와 hashCode 메서드 오버라이딩 방법에 대해 다시 한 번 알게되었습니다.
  • hashCode의 경우 31을 사용해서 hashCode를 만들어 줄 수 있음을 알게되었습니다.
  • 
  • String의 .hashCode() 의 경우 문자열이 같으면 같은 hashCode값을 리턴합니다.

  

 

전체코드

import java.util.*;

// 방이 생성되는 조건
// 이전에 방문했던 정점 && 처음 생긴 선분
// 교차점 처리 (2칸 씩 움직이도록)

class Node{
    int r,c;
    
    public Node(int r,int c){
        this.r = r;
        this.c = c;
    }
    
    @Override
    public boolean equals(Object o){
        if(this==o) return true;
        if(o==null || !(o instanceof Node)) return false;
        Node node = (Node)o;
        if(node.r==this.r && node.c==this.c) return true;
        
        return false;
    }
    
    @Override
    public int hashCode(){
        final int prime = 31;
        int result = 1;
        result = result*prime + r;
        result = result*prime + c;
        return result;
    }
}

class Solution {
    int[] dr = {-1,-1,0,1,1,1,0,-1};
    int[] dc = {0,1,1,1,0,-1,-1,-1};
    int answer;
    Map<Node,List<Node>> map;
    
    void solve(int[] arrows){
        
        Node cur_node = new Node(0, 0);
        map.put(cur_node,new ArrayList<>());
        
        for(int a : arrows){
            for(int i=0;i<2;i++){
                Node next_node = new Node(cur_node.r + dr[a],cur_node.c + dc[a]);
                
                if(!map.containsKey(next_node)){ // 처음 방문하는 지점
                    map.put(next_node,new ArrayList<>());
                }else if(!map.get(next_node).contains(cur_node)){ // 재방문 지점이고 새로 만들어진 선분이면 answer+1
                    answer+=1;
                }
                
                map.get(next_node).add(cur_node);
                map.get(cur_node).add(next_node);
                
                cur_node = next_node;
            }
            
        }
        
    }
    
    public int solution(int[] arrows) {
        answer = 0;
        map = new HashMap<>();
        
        solve(arrows);
        
        return answer;
    }
}