방의 개수 (프로그래머스) JAVA

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

프로그래머스

문제 설명

입력으로는 방향이 주어진다. 이 방향으로 움직였을 때, 방이 생기는지 확인하면 됩니다. 예시로 살펴보면 

주어진 방향대로 움직이면 삼각형 1개, 큰 사각형1개, 평행사변형 1개가 생깁니다.

 

문제에 대한 아이디어

이 문제는 프로그래머스 코딩 테스트 문제 풀이 전략에서 나온 문제입니다. 간선을 지나갔는지 유무를 확인하는 문제를 어떻게 풀어야 할까 고민하고 있었는데  책에 이 문제가 있어 책의 해결책을 공부해봤습니다.

이 문제는 배열의 크기가 10만입니다. 이러면 한 방향으로 10만번 이동 할 수 있고 총 배열의 크기는 20만 * 20만입니다. 그러므로 2차원 배열로 푸는 문제는 아닌 것 같습니다. 그래서 인접 리스트를 이용해 그래프를 표현해야 합니다.

 

방이 생길 조건

• 기존에 방문 했던 정점에 갔을 때
• 이 때 잇고자 하는 두 정점이 이미 이어져 있으면 안됨

즉, 기존에 방문 했던 정점에 도달 했을 때 처음 간 간선 이어야 한다.

 

방이 2개 생길 경우

• 상,하,좌,우로만 움직인다면 방은 무조건 한개가 생깁니다.
• 하지만 대각선으로 움직인다면 두 개의 대각선이 만나 2개의 삼각형이 생길 수 도 있습니다.

이걸 해결하기 위해 2번 움직이면 됩니다. 즉, 모든 크기를 2배 씩으로 하면 대각선으로 움직여도 하나의 도형이 생깁니다.

 

전체 코드

 public static class  Vertex{
        public final int y;
        public final int x;
        public final String id;
        public final Set<String> connectedVertices;
        
        public Vertex(int y, int x){
            this.y = y;
            this.x = x;
            this.id = id(y,x);
            this.connectedVertices = new HashSet<>();
        }
        
        public static String id(int y, int x){
            return String.format("(%d, %d)", y, x);
        }
    }

• Vertex 클래스는 한 점 입니다.
• connectedVertices는 그 정점이 누구랑 연결되어 있는지를 저장하는 Set입니다.
• 이번 책에서 배운 내용은 id를 설정하면 더 편하게 Map에서 관리 할 수 있다는 점 입니다.

public int solution(int[] arrows) {
        int answer = 0;
        Map<String, Vertex> vertices = new HashMap<>();
        Vertex v = new Vertex(0, 0);
        vertices.put(v.id, v);
        
        for(int d : arrows){
            for(int i = 0; i < 2; ++i){
                int ny = v.y + dy[d];
                int nx = v.x + dx[d];
                String id = Vertex.id(ny,nx);
                
                if(!vertices.containsKey(id)){
                    vertices.put(id, new Vertex(ny, nx));
                } else if(!v.connectedVertices.contains(id)){
                    ++answer;
                }
                
                Vertex u = vertices.get(id);
                v.connectedVertices.add(u.id);
                u.connectedVertices.add(v.id);
                v = vertices.get(id);
            }
            
        }
        return answer;
    }

• Map<String, Vertex> 에서 key는 id입니다. 지나간 정점을 확인 할 수 있습니다.
• for문을 2번 도는 것은 모든 크기를 2배로 했기 때문입니다.
• vertices가 key를 포함했다면 즉 한번 갔던 정점이면 v.connectedVertices를 통해 이미 이 간선으로 왔는지 조사합니다.
• 그리고 이전 정점과 다음 정점에 방문한 간선을 추가해 줍니다.