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

문제

문제는 굉장히 간단하다. 문제와 같이 8방향으로 움직여 아래와 같이 방이 만들어지는 갯수를 반환하면 된다.

 

---

풀이방법

- 풀이 시간 : 30분

 

일단 arraws의 크기가 최대 10만개다. 양옆/위아래로 10만개씩 그려주려면 200,000 * 200,000의 배열이 필요하다.

이정도 배열이면 boolean형태여도 메모리가 37GB 정도가 된다.. 메모리 초과가 무조건 난다.

그래서 생각하게 된 방법이 Set을 이용해 방문한 노드를 저장해준다면 map을 그릴 필요도 없고 굉장히 편리해지는거 아닌가? 라는 생각을 했다.

 

그렇게 이미 방문한 노드를 한번 더 방문하게 된다면 + 1 해주는 방식으로 진행했다. 이미 방문한 노드를 방문해야 방이 생긴다고 생각했다.

 

그렇게 짠 코드로 돌려봤지만 역시나 실패였고 내가 생각하지 못한게 2가지 정도가 있었다.

 

1. 대각선 두개가 만드는 방을 생각하지 못했다.

2. 이미 지나온 간선을 한번 더 지나오는 경우를 생각하지 못했다.

 

1번 경우

만약 아래 사진과 같이 대각선 하나가 더 그어졌다고 생각해보자. 양쪽 대각선이 가운데에서 만나고있는데, 저기는 정점이 없다. 이 경우를 생각해 2번씩 이동하게 해주었다. 2번씩 이동하면 대각선도 중앙에서 만날 수 있게 처리가 가능하다.

 

2번 경우

아래 노랑 동그라미를 친것처럼 저부분에서 계속 세모만 그리고 있다고 가정해보겠다.

그럼 내 로직으로는 이미 방문한 노드가 있기때문에 방이 생기지 않아도 +1이 된다. 이러한 경우를 해결하기 위해 이전 위치와 다음위치를 Set에 저장해 함께 가지고 다녔다. 간선의 정보도 가지고 다닌것이다.

 

주의할점은 반대로도 갈 수 있다는 점이다. 만약 내가 (0, 0) -> (1, 0)으로 이동했는데 다시 (1, 0) -> (0, 0)으로 이동하고 또 다시 (0, 0) -> (1, 0)으로 이동만 반복한다 했을때 간선의 정보를 정방향만 저장해준다면 반대편으로 돌아갈때 또 방문한 도시이고 간선이 존재하지 않기때문에 +1이 된다.

 

그래서 정방향과 반댓방향의 간선을 모두 저장해주었다.

 

---

코드

import java.util.*;
import java.io.*;

class Solution {
    static int count;
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
    static Set<String> visited = new HashSet<>();
    static Set<String> edges = new HashSet<>();
    public int solution(int[] arrows) {
        count = 0;
        
        checkRoom(arrows);
        
        return count;
    }
    
    
    private static void checkRoom(int[] dir){
        int x = 0;
        int y = 0;
        
        visited.add(x + "," + y);
            
        for (int d : dir) {
            for (int k = 0; k < 2; k++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                String edge = x + "," + y + "," + nx + "," + ny;
                String reverseEdge = nx + "," + ny + "," + x + "," + y;
                
                if (visited.contains(nx + "," + ny) && !edges.contains(edge)) {
                    count++;
                }
                
                visited.add(nx + "," + ny);
                edges.add(edge);
                edges.add(reverseEdge);
                
                x = nx;
                y = ny;
            }
        }
    }
}