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

💡 문제
방의 개수 (https://school.programmers.co.kr/learn/courses/30/lessons/49190)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

• 그래프 이론: 문제는 좌표 평면에서 주어진 방향에 따라 이동하며 그래프를 형성하는 것으로 볼 수 있습니다. 각 좌표는 정점을, 이동 경로는 간선을 나타냅니다.
• 그래프 탐색 알고리즘: 주어진 방향 배열을 통해 좌표 평면을 탐색하며, 각 이동 경로를 그래프의 간선으로 처리합니다. 이때, 각 정점과 간선의 방문 여부를 관리하기 위해 해싱과 집합(Set)을 사용합니다.
• 좌표 평면에서의 이동: 주어진 8방향 벡터를 사용하여 각 방향으로 좌표를 업데이트하고, 해당 좌표가 이미 방문한 적이 있는지 여부를 검사합니다.
• 해싱과 집합: 해시맵과 집합을 사용하여 각 정점과 간선의 방문 여부를 효율적으로 관리하며, 중복을 방지합니다.
• 알고리즘 구현 능력: 탐색과 업데이트 과정을 정확히 구현하여 문제를 해결하는 데 필요한 코드 작성 능력이 중요합니다.

---

🤓 문제 풀이

🔨 문제 설명

원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다.

ex) 1일때는 오른쪽 위로 이동

그림을 그릴 때, 사방이 막히면 방하나로 샙니다.

이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요.

원점(0,0)에서 시작해서 주어진 방향 배열(arrows)에 따라 이동하며 선을 그립니다. 각 방향은 다음과 같습니다:

• 0: 오른쪽 위 대각선 (↗)
• 1: 위쪽 (↑)
• 2: 왼쪽 위 대각선 (↖)
• 3: 왼쪽 (←)
• 4: 왼쪽 아래 대각선 (↙)
• 5: 아래쪽 (↓)
• 6: 오른쪽 아래 대각선 (↘)
• 7: 오른쪽 (→)

선이 교차하여 닫힌 공간(방)을 만들면 방 하나로 셉니다. 주어진 arrows 배열을 따라 이동했을 때, 형성된 방의 개수를 구하는 문제입니다.

 

• 원점(0,0)에서 시작해서 방향으로 이동하며 선을 그린다:
  • 이는 시작점에서 여러 방향으로 이동하여 경로를 만든다는 것을 의미합니다. 여기서 각 이동 경로는 간선, 이동 후의 점은 정점으로 생각할 수 있습니다.
• 이동하는 방향이 담긴 배열 arrows가 매개변수로 주어진다:
  • 이는 방향에 따라 이동하며 경로를 만든다는 것을 나타내며, 이 경로를 추적해야 한다는 것을 의미합니다.
• 사방이 막히면 방 하나로 샌다:
  • 이는 이동 경로가 다시 자신을 만나 닫힌 경로(사이클)가 형성될 때 방을 하나로 센다는 의미입니다. 닫힌 경로를 찾는 것은 그래프에서 사이클을 찾는 문제와 같습니다.

그래프 알고리즘을 선택한 이유는 이동 경로를 정점과 간선으로 모델링하고, 이 과정에서 사이클을 찾아 방의 개수를 계산해야 하기 때문입니다. 이는 전형적인 그래프 이론 문제입니다.

---

🔨 접근 방법

1. 현재 위치와 이동 방향을 기록합니다.
2. 이미 방문한 경로와 정점을 추적하여 새로운 방이 형성되는지를 검사합니다.

---

🔨 문제 풀이 과정

• 각 좌표와 방향을 추적하기 위해 좌표 정보를 저장하는 자료 구조가 필요합니다.
• 이동하면서 각 경로(간선)와 정점이 이미 방문되었는지 체크합니다.
• 새로운 간선이 생성되고, 해당 간선이 이미 존재하는 경우 새로운 방이 형성되었음을 의미합니다.

---

🔨 그래프 이론을 이용한 접근 방식

그래프 이론을 활용하여 이동 경로를 그래프의 간선으로 보고, 교차점(정점)이 생성될 때 방이 만들어지는지를 판단합니다. 문제의 본질이 정점과 간선으로 이루어진 구조에서 닫힌 경로(사이클)를 찾는 것이기 때문입니다.

• 정점(Vertex)과 간선(Edge)의 정의:
  • 각 좌표를 정점으로 생각합니다.
  • 두 좌표 사이의 이동 경로를 간선으로 봅니다.
• 방문한 정점과 간선의 추적:
  • 현재 위치와 이동 방향을 기록합니다.
  • 이미 방문한 경로(간선)와 정점을 추적하여 새로운 방이 형성되는지를 검사합니다.
• 교차점(Intersection)의 판별:
  • 이미 방문한 정점으로 새로운 간선이 만들어질 때, 이는 방을 형성하는 교차점이 됩니다.
• 이동 경로 추적: 주어진 방향 배열에 따라 이동하면서 선을 긋는 과정은 각 좌표를 정점(Vertex)으로 보고, 이동 경로를 간선(Edge)으로 생각할 수 있습니다.
• 교차점과 닫힌 경로: "선을 그릴 때, 사방이 막히면 방 하나로 샌다."는 문장은 그래프 이론에서 사이클을 찾는 문제와 일치합니다. 이동하면서 이미 방문한 경로와 새롭게 형성되는 경로를 추적하여 닫힌 경로가 생성되는지 확인해야 합니다.
• 방문한 좌표와 경로 관리: 정점과 간선을 이용하여 방문 여부를 체크하는 것은 그래프 탐색 알고리즘에서 흔히 사용되는 방법입니다. 이를 통해 새로운 방이 생성되는지 확인할 수 있습니다.

---

🔨 구현코드

import java.util.*;

class Solution {
    public int solution(int[] arrows) {
        int answer = 0;

        // 방문한 점과 간선 정보를 저장할 Set들
        Set<String> visitedPoints = new HashSet<>();
        Set<String> visitedEdges = new HashSet<>();
        
        // 초기 위치
        int x = 0, y = 0;
        // 이전 위치 초기화
        int prevX = 0, prevY = 0;
        
        // 초기 위치 방문 처리
        visitedPoints.add(x + "," + y);

        // 방향 벡터 정의 (8방향)
        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: ↖
        };

        // arrows 배열 순회
        for (int arrow : arrows) {
            for (int i = 0; i < 2; i++) {
                // 새로운 좌표 계산
                int nx = x + directions[arrow][0];
                int ny = y + directions[arrow][1];
                
                // 현재 점과 다음 점을 문자열로 표현
                String curPoint = nx + "," + ny;
                String edge1 = x + "," + y + "|" + curPoint;
                String edge2 = curPoint + "|" + x + "," + y;
                
                // 현재 점을 방문한 적이 있는지 확인
                if (visitedPoints.contains(curPoint)) {
                    // 방문한 간선인지 확인
                    if (!visitedEdges.contains(edge1) && !visitedEdges.contains(edge2)) {
                        answer++;
                    }
                }

                // 현재 점과 간선을 방문 기록에 추가
                visitedPoints.add(curPoint);
                visitedEdges.add(edge1);
                visitedEdges.add(edge2);

                // 이전 위치 업데이트
                prevX = x;
                prevY = y;
                // 현재 위치 업데이트
                x = nx;
                y = ny;
            }
        }

        return answer;
    }
}

---

📚 풀이 보완

코드 설명

• 방향 벡터 정의: 각 방향(0~7)에 대해 이동할 좌표의 변화를 정의합니다.
• 자료 구조 준비:
  • vertices는 방문한 정점을 기록합니다.
  • edges는 방문한 간선을 기록합니다.
• 초기 위치 설정: 원점(0,0)을 시작점으로 설정하고 vertices에 추가합니다.
• 이동 처리: arrows 배열의 각 방향에 대해 이동합니다. 각 이동은 두 번씩 수행하여 교차점을 정확하게 찾습니다.
• 정점과 간선 기록: vertices와 edges는 각각 Set<String>으로 관리됩니다. vertices는 방문한 정점들을 저장하고, edges는 방문한 간선들을 저장합니다. 간선은 두 점을 연결하는 방향에 따라 정해진 형식으로 저장됩니다.
  • 새 정점인 경우 vertices에 추가합니다.
  • 이미 방문한 정점이지만 새 간선인 경우 방이 추가되었음을 의미합니다.
  • 간선을 edges에 추가합니다.
• 현재 위치 갱신: 다음 위치로 이동합니다.
• 방의 개수 반환: 최종적으로 방의 개수를 반환합니다.
  • vertices.contains(vertex)를 통해 새로운 정점인 경우만 추가하고, 이미 방문한 정점이면서 간선이 새로운 경우에만 answer를 증가시킵니다. 이는 간선이 중복되는 경우를 방지하며 방의 개수를 세는 데 도움이 됩니다.

---

📍 Plus+

시간 복잡도

공간 복잡도

요약

• 공간 복잡도: O(V + E) (V는 점의 개수, E는 간선의 개수)
• 시간 복잡도: O(N) (N은 arrows 배열의 길이)

 

---

문제 풀이 회고..

 

이 문제는 실제로 복잡도가 높은 문제 중 하나입니다. 주어진 화살표 방향에 따라 그래프를 그리고, 그래프 상에서 방문한 간선의 수를 계산하는 문제입니다.

1. 그래프 이론의 응용: 문제를 해결하기 위해 그래프 이론을 이해하고 적용해야 합니다. 특히 여기서는 그래프의 정점과 간선을 동시에 관리하고, 이들이 어떻게 상호작용하는지를 이해해야 합니다.
2. 복잡한 방향 처리: 화살표 방향이 8방향으로 주어지며, 이를 바탕으로 다음 위치를 계산해야 합니다. 각 방향마다 다음 위치를 계산하는 로직을 정확히 구현해야 합니다.
3. 공간 복잡도 관리: 방문한 점과 간선을 관리할 때, 메모리 사용량을 효율적으로 관리해야 합니다. 그래프의 크기에 따라 메모리 소비가 급증할 수 있기 때문에 이를 효율적으로 처리하는 것이 중요합니다.
4. 문자열 처리와 해시셋 활용: 좌표를 문자열로 표현하고, 해시셋을 사용하여 중복 방지 및 빠른 검색을 처리해야 합니다. 이 과정에서 문자열 연산의 효율성과 해시셋의 사용법을 잘 알아야 합니다.