문제 요약
N x M 크기의 격자가 주어진다.
각 칸은 정사각형이고, 칸 안에는 대각선이 하나 그어져 있다.
대각선 방향은 두 가지다.
1:/방향-1:\방향
각 칸은 대각선에 의해 두 개의 삼각형으로 나뉜다.
우리는 각 칸에서 두 삼각형 중 정확히 하나만 색칠할 수 있다.
색칠한 삼각형들은 한 변을 공유하면 서로 연결된다.
목표는 적절히 색칠했을 때 만들 수 있는 연결된 삼각형 덩어리 중 가장 큰 넓이를 구하는 것이다.
각 삼각형의 넓이는 1이므로, 결국 가장 큰 덩어리에 포함된 삼각형 개수를 구하면 된다.
핵심 아이디어
이 문제는 격자를 그대로 보려고 하면 어렵다.
대신 각 칸의 두 삼각형을 각각 하나의 그래프 노드로 생각하면 훨씬 단순해진다.
각 칸에는 삼각형이 2개 있으므로 전체 노드 수는 다음과 같다.
2 * N * M그리고 서로 한 변을 공유하는 삼각형끼리 그래프에서 간선을 연결한다.
그러면 문제는 다음과 같이 바뀐다.
삼각형 그래프에서 연결된 노드들 중, 같은 칸에서 나온 삼각형을 동시에 고르지 않으면서 만들 수 있는 가장 긴 연결 구간을 찾기
왜 그래프로 바꿀 수 있을까?
삼각형 두 개가 연결되려면 서로 한 변을 공유해야 한다.
이는 격자에서 상하좌우로 인접한 칸 사이에서만 발생한다.
따라서 각 삼각형을 노드로 보고, 변을 공유하는 삼각형끼리 간선을 연결하면 연결 관계를 그대로 표현할 수 있다.
중요한 점은 하나의 삼각형은 바깥쪽 변을 최대 두 개만 가진다는 것이다.
따라서 그래프에서 각 삼각형 노드의 차수는 최대 2이다.
즉, 전체 그래프는 여러 개의 다음 구조로 나뉜다.
- path 형태
- cycle 형태
- 고립된 노드
그래서 복잡한 그래프 탐색 문제가 아니라, path 또는 cycle에서 조건을 만족하는 가장 긴 구간을 찾는 문제로 바뀐다.
삼각형 상태 정의하기
각 칸의 삼각형을 두 개의 상태로 나눈다.
각 삼각형은 정사각형의 네 방향 중 두 방향의 변을 가진다.
방향은 다음처럼 표현하자.
UP = 0
RIGHT = 1
DOWN = 2
LEFT = 3/ 방향 대각선
grid[i][j] == 1이면 / 방향이다.
/ 이때 두 삼각형은 다음 방향을 가진다.
state 0: UP, LEFT
state 1: DOWN, RIGHT\ 방향 대각선
grid[i][j] == -1이면 \ 방향이다.
\이때 두 삼각형은 다음 방향을 가진다.
state 0: UP, RIGHT
state 1: DOWN, LEFT즉, 어떤 칸에서 특정 방향의 변을 가진 삼각형이 몇 번 상태인지 알 수 있으면 인접한 칸과 간선을 연결할 수 있다.
인접한 삼각형 연결하기
서로 오른쪽으로 인접한 두 칸을 생각해보자.
왼쪽 칸의 오른쪽 변을 가진 삼각형과, 오른쪽 칸의 왼쪽 변을 가진 삼각형은 서로 한 변을 공유한다.
따라서 두 삼각형 노드를 연결한다.
왼쪽 칸의 RIGHT 삼각형 <-> 오른쪽 칸의 LEFT 삼각형상하로 인접한 두 칸도 마찬가지다.
위 칸의 DOWN 삼각형 <-> 아래 칸의 UP 삼각형이렇게 모든 인접한 칸에 대해 간선을 추가하면 전체 삼각형 그래프를 만들 수 있다.
같은 칸의 두 삼각형은 동시에 고를 수 없다
문제 조건에서 각 칸에서는 두 삼각형 중 정확히 하나만 색칠할 수 있다.
따라서 어떤 연결 덩어리를 만들 때 같은 칸에서 나온 두 삼각형이 동시에 포함되면 안 된다.
삼각형 그래프의 각 연결 요소는 path 또는 cycle 형태이므로, 연결 덩어리는 그 안의 연속된 구간으로 볼 수 있다.
결국 각 연결 요소마다 다음 문제를 풀면 된다.
path 또는 cycle로 나열된 삼각형들에서, 같은 칸 번호가 중복되지 않는 가장 긴 연속 구간을 찾기
이 문제는 슬라이딩 윈도우로 해결할 수 있다.
슬라이딩 윈도우
각 삼각형 노드가 어느 칸에서 나온 것인지 cell_id로 나타낸다.
예를 들어 연결 요소가 다음과 같다고 하자.
cell_id: 0, 1, 2, 1, 3여기서 같은 칸 번호 1이 두 번 등장한다.
하나의 덩어리에는 같은 칸의 삼각형을 두 개 넣을 수 없으므로, 중복이 없는 가장 긴 연속 구간을 찾아야 한다.
이때 투 포인터 또는 슬라이딩 윈도우를 사용한다.
윈도우 안에 같은 cell_id가 두 번 들어오면 왼쪽 포인터를 이동시켜 중복을 제거한다.
cycle 형태의 연결 요소는 시작점과 끝점이 이어져 있으므로 배열을 두 번 이어 붙여서 처리한다.
단, cycle에서 선택할 수 있는 길이는 전체 cycle 길이를 넘을 수 없다.
전체 코드
def solution(grid):
n = len(grid)
m = len(grid[0])
node_count = 2 * n * m
graph = [[] for _ in range(node_count)]
def cell_id(row, col):
return row * m + col
def node_id(row, col, state):
return cell_id(row, col) * 2 + state
def state_for_direction(row, col, direction):
# direction: 0=UP, 1=RIGHT, 2=DOWN, 3=LEFT
if grid[row][col] == 1:
# / 방향: state 0 = UP, LEFT / state 1 = DOWN, RIGHT
if direction in (0, 3):
return 0
return 1
# \ 방향: state 0 = UP, RIGHT / state 1 = DOWN, LEFT
if direction in (0, 1):
return 0
return 1
def add_edge(a, b):
graph[a].append(b)
graph[b].append(a)
for row in range(n):
for col in range(m):
if col + 1 < m:
left_node = node_id(row, col, state_for_direction(row, col, 1))
right_node = node_id(row, col + 1, state_for_direction(row, col + 1, 3))
add_edge(left_node, right_node)
if row + 1 < n:
upper_node = node_id(row, col, state_for_direction(row, col, 2))
lower_node = node_id(row + 1, col, state_for_direction(row + 1, col, 0))
add_edge(upper_node, lower_node)
def longest_unique_segment(cell_ids, is_cycle):
length = len(cell_ids)
array = cell_ids * 2 if is_cycle else cell_ids
count = {}
left = 0
best = 0
for right, current_cell in enumerate(array):
count[current_cell] = count.get(current_cell, 0) + 1
while count[current_cell] > 1 or right - left + 1 > length:
left_cell = array[left]
count[left_cell] -= 1
if count[left_cell] == 0:
del count[left_cell]
left += 1
best = max(best, right - left + 1)
return best
visited = [False] * node_count
answer = 1
for start in range(node_count):
if visited[start]:
continue
component = []
stack = [start]
visited[start] = True
while stack:
current = stack.pop()
component.append(current)
for next_node in graph[current]:
if not visited[next_node]:
visited[next_node] = True
stack.append(next_node)
is_cycle = all(len(graph[node]) == 2 for node in component)
if is_cycle:
ordered_start = component[0]
else:
ordered_start = component[0]
for node in component:
if len(graph[node]) < 2:
ordered_start = node
break
ordered_cell_ids = []
previous = -1
current = ordered_start
while True:
ordered_cell_ids.append(current // 2)
next_node = -1
for neighbor in graph[current]:
if neighbor != previous:
next_node = neighbor
break
if next_node == -1:
break
previous = current
current = next_node
if current == ordered_start:
break
answer = max(answer, longest_unique_segment(ordered_cell_ids, is_cycle))
return answer예제 1
grid = [
[-1, -1, -1],
[1, 1, -1],
[1, 1, 1],
]이 격자에서 가능한 가장 큰 삼각형 덩어리의 넓이는 5이다.
따라서 결과는 다음과 같다.
5예제 2
grid = [
[1, -1, 1],
[-1, 1, -1],
]가능한 가장 큰 삼각형 덩어리의 넓이는 4이다.
4예제 3
grid = [[1]]칸이 하나뿐이므로 삼각형 하나만 색칠할 수 있다.
따라서 결과는 1이다.
1시간 복잡도
격자의 칸 개수를 K = N * M이라고 하자.
각 칸마다 삼각형 노드가 2개 있으므로 노드 수는 2K이다.
각 인접 관계는 오른쪽과 아래쪽만 확인하면 되므로 간선 수도 O(K)이다.
그래프 생성, 연결 요소 탐색, 슬라이딩 윈도우 모두 전체 노드와 간선을 한 번씩 보는 수준이다.
따라서 시간 복잡도는 다음과 같다.
O(N * M)공간 복잡도도 그래프와 방문 배열을 저장하므로 다음과 같다.
O(N * M)제한 조건에서 N * M <= 200,000이므로 충분히 처리할 수 있다.
정리
이 문제의 핵심은 삼각형을 직접 색칠해보는 것이 아니라, 삼각형 간의 연결 관계를 그래프로 바꾸는 것이다.
풀이의 핵심 포인트는 다음과 같다.
- 각 칸의 두 삼각형을 각각 그래프 노드로 본다.
- 변을 공유하는 삼각형끼리 간선을 연결한다.
- 각 삼각형 노드는 최대 2개의 이웃만 가지므로 연결 요소는 path 또는 cycle이 된다.
- 같은 칸에서 나온 두 삼각형은 동시에 고를 수 없다.
- 따라서 각 연결 요소에서 같은
cell_id가 중복되지 않는 가장 긴 연속 구간을 찾는다. - 이 구간 길이가 만들 수 있는 삼각형 덩어리의 넓이다.
그래프 모델링만 잘 떠올리면 이후에는 연결 요소 탐색과 슬라이딩 윈도우로 해결할 수 있다.
