[알고리즘 문제] 그래프 - 프로그래머스 방의 개수(level 5)

문제 이해

원점에서 시작해 0부터 7까지의 방향 명령을 따라 선을 긋습니다. 그 과정에서 선으로 완전히 둘러싸인 영역, 즉 방이 몇 개 생기는지 구해야 합니다.

7   0   1
 \  |  /
6 - * - 2
 /  |  \
5   4   3

명령의 수는 최대 100,000개입니다. 모든 영역을 격자에 그린 뒤 내부를 탐색하기보다, 경로가 만드는 그래프의 변화를 직접 추적해야 합니다.

경로를 그래프로 보기

이동 경로의 요소를 그래프 용어로 바꾸면 필요한 정보가 명확해집니다.

현재 위치와 도착 위치: 정점(Vertex)
두 위치를 연결하며 그은 선: 간선(Edge)
선으로 둘러싸여 새로 생긴 영역: 사이클(Cycle)

시작점부터 하나로 연결된 경로에 새 간선 하나를 추가할 때, 그 간선이 이미 존재하는 두 정점을 연결하면 새로운 사이클이 하나 생깁니다. 따라서 실제 영역을 채워 보지 않아도 정점과 간선의 방문 여부만으로 방의 수를 셀 수 있습니다.

방이 생기는 조건

현재 정점에서 다음 정점으로 이동할 때 아래 두 조건을 동시에 만족하면 방이 하나 추가됩니다.

1. 다음 정점이 이미 방문한 정점이다.
2. 현재 정점과 다음 정점을 잇는 간선은 처음 지나는 간선이다.

if (visited.count(nextPoint) &&
    !edges.count({current, nextPoint})) {
    ++answer;
}

방문했던 정점에 도착하더라도 같은 간선을 되짚어 간다면 새로운 경계가 생기지 않습니다. 정점뿐 아니라 간선의 방문 여부도 함께 확인해야 중복으로 방을 세지 않습니다.

정점과 간선 저장하기

처음에는 방문한 좌표와 간선을 vector에 저장하는 방법을 생각했습니다. 그러나 방문 여부를 매번 선형 탐색하면 명령이 최대 N개일 때 전체 시간이 최악의 경우 O(N²)까지 늘어납니다.

using Point = pair<int, int>;
using Edge = pair<Point, Point>;

set<Point> visited;
set<Edge> edges;

정렬된 set을 사용하면 삽입과 조회를 O(log N)에 처리할 수 있습니다. 간선은 방향이 없으므로 (A, B)와 (B, A)가 같은 간선입니다. 조회를 단순하게 유지하기 위해 이동할 때 두 방향을 모두 저장합니다.

edges.insert({current, nextPoint});
edges.insert({nextPoint, current});

using Point = pair<int, int>;처럼 별칭을 만들면 중첩된 pair의 의미를 이름으로 드러내 코드의 가독성을 높일 수 있습니다.

대각선 교차점 처리

정수 좌표만 한 칸씩 이동하면 서로 반대 방향의 대각선 두 개가 칸의 중앙에서 교차해도 그 지점을 정점으로 기록하지 못합니다. 교차점에서 방이 나뉘는 경우를 놓치게 되는 이유입니다.

한 번만 이동: (0, 0) → (1, 1)
두 번으로 분할: (0, 0) → (1, 1) → (2, 2)

각 방향 명령을 같은 방향으로 두 번 실행하면 전체 좌표계를 두 배로 확대한 것과 같습니다. 원래 반 칸 위치에 있던 대각선 교차점이 정수 좌표가 되어 일반 정점과 같은 방식으로 방문 여부를 검사할 수 있습니다. 경로의 모양과 방의 개수는 그대로 유지됩니다.

최종 코드

#include <set>
#include <utility>
#include <vector>

using namespace std;
using Point = pair<int, int>;
using Edge = pair<Point, Point>;

int solution(vector<int> arrows)
{
    const Point directions[8] = {
        {0, 1}, {1, 1}, {1, 0}, {1, -1},
        {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}
    };

    int answer = 0;
    Point current = {0, 0};

    set<Point> visited;
    set<Edge> edges;
    visited.insert(current);

    for (int arrow : arrows) {
        for (int step = 0; step < 2; ++step) {
            Point nextPoint = {
                current.first + directions[arrow].first,
                current.second + directions[arrow].second
            };

            if (visited.count(nextPoint) &&
                !edges.count({current, nextPoint})) {
                ++answer;
            }

            visited.insert(nextPoint);
            edges.insert({current, nextPoint});
            edges.insert({nextPoint, current});

            current = nextPoint;
        }
    }

    return answer;
}

시작점은 이동 전에 방문 집합에 넣습니다. 이후 각 명령을 두 단계로 나누고, 새 간선으로 방문 정점에 들어가는지를 먼저 확인한 다음 정점과 양방향 간선을 기록합니다. 이 순서를 지켜야 현재 이동을 새 간선으로 정확히 판별할 수 있습니다.

복잡도

명령의 수를 N이라 하면 실제 이동은 2N번입니다. 각 이동에서 set 조회와 삽입을 상수 번 수행하므로 시간복잡도는 O(N log N), 저장하는 정점과 간선의 수는 이동 횟수에 비례하므로 공간복잡도는 O(N)입니다.

해시 함수를 정의한 unordered_set을 사용하면 평균 O(N) 시간도 기대할 수 있지만, 이 풀이에서는 pair를 바로 비교할 수 있고 구현이 간단한 set을 선택했습니다.

정리

• 이동 좌표를 정점, 그은 선을 간선으로 모델링한다.
• 방문한 정점에 처음 지나는 간선으로 들어갈 때 방이 하나 생긴다.
• 무방향 간선을 양방향으로 저장해 같은 선을 다시 지나는 경우를 제외한다.
• 각 이동을 두 번으로 나눠 대각선 교차점도 정점으로 처리한다.
• set으로 방문 정보를 관리해 전체 시간복잡도를 O(N log N)으로 유지한다.

핵심은 방의 내부를 직접 찾는 대신 방이 생기는 순간을 그래프의 새 사이클로 바꿔 생각하는 것입니다. 정점과 간선만으로 문제를 단순화한 뒤, 대각선 교차라는 예외를 좌표 확대 하나로 같은 규칙 안에 포함할 수 있었습니다.