BOJ 10026) Cow art + 문자열을 문자 단위로 분할

Wonjun Lee·2024년 6월 12일

BFS DFS Graph ps

문제 링크)

https://www.acmicpc.net/problem/10026

입력

Line 1: The integer N.
Lines 2..1+N: Each line contains a string with N characters, describing one row of a painting.

출력

Line 1: Two space-separated integers, telling the number of regions in the painting when viewed by a human and by a cow.

풀이과정

문제이해

문제에서는 적녹 색맹인 소의 관점에서 구분 할 수 있는 색상 영역의 수와 사람이 구분 가능한 색상 영역 수를 구하라고 한다.

영역을 나누는 경계는 색상이 달라지는 지점이다. 따라서 같은 색상인 곳을 검사하면서 다른 영역을 찾는 탐색을 적용하는 것이 옳을 것 같다.

입력의 개수는 NXN이며, N <= 100의 조건을 가지므로, 최대 10000개의 입력이 들어올 것이다.

순회 방식을 사용하면 O(N)의 시간복잡도를 갖게 되므로 시간 내에 풀이 할 수 있을 것이다. O(N*N)의 시간복잡도는 시간초과를 만들 가능성이 높다.

접근방법

사람이 보는 영역의 개수 <= 소가 보는 영역의 개수

위 조건이 성립한다면 굳이 사람이 보는 영역단위로 순회를 하는 것보단 더 넓을 수 있는 소의 기준에서 순회를 하는 편이 효율적으로 보인다. 왜냐하면, 소가 보는 영역이 1개일 때에도 사람이 보는 영역은 최대 10000개 까지 나뉠수도 있기 때문이다.

RGRGRGRGRGRG....RG
GRGRGRGRGRGR....GR
RGRGRGRGRGRG....RG
...
GRGRGRGRGRGR....GR -> 소는 전체 영역이 같은 색으로 보인다.

따라서 소의 관점에서 순회하되 R이나 G로 색칠된 부분 영역의 순회를 마친 뒤 사람 기준 영역 수를 1 증가시키면 될 것이다.

이런 방식은 색상 경계 노드들에 대해 2번의 방문을 수행하게 된다.
(다른 색상인 경우 따로 저장해두고, 이후 이 색상 영역을 순회할 때 한 번 방문하고, 추후 저장해둔 노드가 방문되었는지 확인)

따라서 시간복잡도는 O(2*N)이 될 것이고, O(N)에 근사할 수 있다.

코드 설계

일단 NXN개의 색상들을 암시적 그래프로 취급하여 grid라는 2차원 리스트로 저장한다.

그리고 마지막 칸까지 반복적으로 방문했는지 체크하고, 방문하지 않았으면 BFS 알고리즘을 수행한다.(DFS라도 상관 없다.)

BFS알고리즘을 수행하면서 현재 검사하는 색이 B라면 단순 BFS를 수행한 뒤 사람, 소 영역수를 1씩 증가시킨다.

검사하는 색이 G, R 중 하나라면 같은 색상인 경우 현재 순회하는 큐에 저장하고, 다른 색상이면 버퍼에 저장한다.

큐가 비었다면 버퍼를 검사해서 방문하지 않은 노드를 꺼내 큐에 삽입한다. 이때 색상이 바뀐것을 의미하므로 사람 영역 수를 1 증가시킨다.

이 과정을 버퍼와 큐가 모두 빌 때까지 반복한 뒤 소의 영역 수를 1 증가시킨다.

아래는 이것을 구현한 프로그램이다.

import sys
from collections import deque
def solve() :
   N = int(sys.stdin.readline())
   grid = []
   for i in range(N) :
       grid.append(list(sys.stdin.readline().strip()))
       
   
   regions = { 'human' : 0, 'cow' : 0 }
   steps = ((-1, 0), (1, 0), (0, -1), (0, 1))
   visited = set()
   
   def BFS(row, col) :
       queue = deque()
       queue.append((row, col))
       second_queue = deque()
       visited.add((row, col))
       while queue :
           curr_row, curr_col = queue.popleft()
           for s in steps :
               next_row, next_col = curr_row + s[0], curr_col + s[1]
               if 0 <= next_row and next_row < N and 0 <= next_col and next_col < N and (next_row, next_col) not in visited :
                   if grid[curr_row][curr_col] == grid[next_row][next_col] :
                       queue.append((next_row, next_col))
                       visited.add((next_row, next_col))
                   elif grid[curr_row][curr_col] != 'B' and grid[next_row][next_col] != 'B' :
                       second_queue.append((next_row, next_col))
           if not queue :
               regions['human'] += 1
               if second_queue :
                   next_row, next_col = second_queue.popleft()
                   while second_queue and (next_row, next_col) in visited :
                       next_row, next_col = second_queue.popleft()
                   if (next_row, next_col) not in visited :
                       visited.add((next_row, next_col))
                       queue.append((next_row, next_col))
       
       regions['cow'] += 1
   
   for i in range(N) :
       for j in range(N) :
           if (i, j) not in visited :
               BFS(i, j)
   print(regions['human'], regions['cow'])

solve()