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

문제 소개

오늘 풀었던 프로그래머스 - 방의 개수 문제를 정리합니다.

이 문제는 원점에서 시작해 8방향으로 선을 그려가며 이동할 때,
새로운 방이 몇 개 생기는지를 구하는 문제입니다.

문제 링크: 방의 개수 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 각 점(좌표)은 노드(node), 두 점을 잇는 선은 간선(edge)로 보고, 그래프처럼 모델링합니다.
2. 이동 경로 중, 이미 방문한 노드를 새롭게 다른 경로로 들어갔을 때 방이 생긴다는 특성을 이용합니다.
3. 사선 이동이 있는 그래프이기 때문에, 꼭지점 교차(중간 점)를 방지하기 위해 2번씩 이동합니다.
   

---

해결 과정 및 코드

핵심 아이디어

1. 방향은 총 8방향(0~7), (상, 우상, 우, 우하, 하, 좌하, 좌, 좌상)
2. nodes: 방문한 좌표 기록 (정점)
3. edges: 방문한 간선 기록 (선분, 양방향 저장)
4. 방 생성 조건: 이미 방문한 노드인데, 처음 지나는 간선이면 새로운 방 생성
   
   • 노드 A에서 B로 이동할 때:
     • B를 이전에 방문한 적 있음
     • 하지만 A-B 간선은 처음 지나는 경우 → 사이클(방) 생성
   • 즉, 이미 가본 곳을 다른 경로로 들어가며 닫히는 경우, 방이 생긴다고 볼 수 있음
   • 이중 간선(양방향 저장)을 통해 A→B, B→A 모두 탐색 가능하게 해야 함

코드

시간 복잡도: O(N) (N은 arrows.length, 최대 100,000)

• 각 방향마다 2번 이동하므로 최대 200,000개의 노드/간선 처리

import java.util.*;

class Solution {
    public int solution(int[] arrows) {
        // 8방향
        int[][] dir = {
            {0, 1}, {1, 1}, {1, 0}, {1, -1},
            {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}
        };

        Set<String> nodes = new HashSet<>(); // 방문한 점
        Set<String> edges = new HashSet<>(); // 방문한 선분
        int roomCount = 0;

        int x = 0, y = 0;
        nodes.add(posStr(x, y));

        for (int arrow : arrows) {
            for (int i = 0; i < 2; i++) { // 교차 방지: 방향마다 2번 이동
                int nx = x + dir[arrow][0];
                int ny = y + dir[arrow][1];

                String from = posStr(x, y);
                String to = posStr(nx, ny);
                String edge1 = from + ":" + to;
                String edge2 = to + ":" + from; // 양방향 처리

				// 방이 생기는 조건
                if (nodes.contains(to) && !edges.contains(edge1) && !edges.contains(edge2)) {
                    roomCount++;
                }

                nodes.add(to);
                edges.add(edge1);
                edges.add(edge2);

                x = nx;
                y = ny;
            }
        }

        return roomCount;
    }

	// 좌표를 문자열로 변환
    private String posStr(int x, int y) {
        return x + "," + y;
    }
}