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

[그래프]-방의 개수

프로그래머스

 

문제 설명

방의 개수 구하기(그림을 그릴 때 사방이 막히면 방하나로 간주)

입출력 예시

arrows	result
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]	3

 

풀이 방법(다른 풀이 참고함)

우선 방의 생성 조건을 분석하면, 이미 방문한 정점을 다시 방문하는 경우 하나의 방이 생성된다.

하지만, 아래와 같이 이미 방문한 정점이지만 이미 지나온 간선을 통해 오는 경우는 방의 생성 조건에 해당되지 않는다.

 

즉, 방의 생성 조건은 아래 2가지를 모두 만족해야 한다.

1. 이미 방문한 정점을 다시 방문하는 경우
2. 방문하는 간선이 처음 오는 간선인 경우

또 하나 고려해야 하는 점이 대각선 방향으로도 이동 가능하다는 점이다.

이 부분을 고려해, 그래프를 2배로 넓혀 겹치는 부분이 발생하지 않도록 할 수 있음

헷갈렸던 부분,,

예를 들어 arrows = [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 6, 6, 4, 2, 2, 2, 0]인 경우, 이미 방문한 정점 & 이미 방문한 경로는 방의 개수에 카운트가 되지 않는데 이 예제로 하게 되면 방의 최종적으로 2개가 생기는게 아닐까?(실제로는 방 3개 생성)

라고 생각함

마지막 0 방향으로 했을 때 세 번째 방이 생성되는 것이 아니라, 21번째 인덱스에 있는 2 방향때 세 번째 방이 생성되는 것!

 

코드

import java.util.*;

class Solution {
    static int[][] directions = {
        {0, 1}, // 0
        {1, 1}, // 1
        {1, 0}, // 2
        {1, -1}, // 3
        {0, -1}, // 4
        {-1, -1}, // 5
        {-1, 0}, // 6
        {-1, 1} // 7
    };
    
    public int solution(int[] arrows) {
        int answer = 0;
        
        // 정점 방문 여부 확인을 위한 해시Set 이용
        Set<String> visitedNode = new HashSet<>();
        // 간선 방문 여부 확인을 위한 해시Set 이용
        Set<String> visitedEdge = new HashSet<>();
        
        int currentX = 0;
        int currentY = 0;
        // 시작 위치(0, 0) 정점 방문 표시
        visitedNode.add(String.format("%d/%d", currentX, currentY));
        
        for(int arrow : arrows) {
            // 그래프를 2배로 스케일업(대각선 이동 경로를 위해)
            for(int i=0; i<2; i++) {
                int nextX = currentX + directions[arrow][0];
                int nextY = currentY + directions[arrow][1];
            
                String nextNode = String.format("%d/%d", nextX, nextY);
                String currentToNext = String.format("%d/%d/%d/%d", currentX, currentY, nextX, nextY);
                // 이미 방문한 정점이면서, 새로운 간선으로 이동한 경우 => 방 하나 생성
                if(visitedNode.contains(nextNode) 
                && !visitedEdge.contains(currentToNext)){
                    answer++; // 방 생성
                }
            
                visitedNode.add(nextNode); // 다음 이동 좌표 방문 표시
                visitedEdge.add(currentToNext); // 현재 위치 -> 다음 위치 경로 표시
                String nextToCurrent = String.format("%d/%d/%d/%d", nextX, nextY, currentX, currentY); // 반대 이동 경로인 다음 위치 -> 현재 위치 경로 표시
                visitedEdge.add(nextToCurrent);

                currentX = nextX;
                currentY = nextY;
            }
        }

        return answer;
    }
}

---

참고 사이트

https://yabmoons.tistory.com/606

[ 프로그래머스 방의 개수 (Lv5) ] (C++)