백준 10026번 적록색약

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #그래프 이론 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색

---

조건

시간 제한	메모리 제한
1 초	128 MB

---

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

---

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

---

예제 입출력 1

입력

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

출력

4 3

---

코드(파이썬)

import sys

sys.setrecursionlimit(10**5)

def dfs(x, y, color):
    d = [(1, 0), (0, -1), (-1, 0), (0, 1)]
    visited[color].add((x, y))
    
    for next_x, next_y in [(x+dx, y+dy) for dx, dy in d]:
        if 0 <= next_x < n and 0 <= next_y < n and\
           (next_x, next_y) not in visited[color] and img[next_x][next_y] in color:
            stack.append((next_x, next_y))
            dfs(next_x, next_y, color)
            stack.pop()
            
    return result

visited = dict(zip(["RG", "R", "G", "B"], [set(), set(), set(), set()]))
result = dict(zip(["RG", "R", "G", "B"], [0, 0, 0, 0]))

n = int(sys.stdin.readline())
img = [list(line.rstrip('\n')) for line in sys.stdin.readlines()]

for i in range(n):
    for j in range(n):
        for color in result:
            if img[i][j] in color and (i, j) not in visited[color]:
                stack = list()
                dfs(i, j, color)
                result[color] += 1
                
print(result["R"]+result["G"]+result["B"], result["RG"]+result["B"])

---

특이사항

• 풀이 대부분이 DFS
• 내 코드(36,020KB, 116ms)에 비해 우수한 코드(바로가기, 33,800KB, 92ms)와 비교

  • import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    
    
    def dfs(cur_x, cur_y, color):
        global visit, cnt, graph, dir, color_dic
    
        for x, y in dir:
            nx = cur_x + x
            ny = cur_y + y
            if 0 <= nx < n and 0 <= ny < n and not visit[nx][ny] and color_dic[graph[nx][ny]] == color_dic[color]:
                visit[nx][ny] = True
                dfs(nx, ny, color)
    
    
    n = int(input())
    dir = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    graph = [input().strip() for _ in range(n)]
    
    flag = 0
    
    for i in range(2):
        color_dic = {
            'R': 1,
            'G': 2,
            'B': 3,
        }
        cnt = 0
        visit = [[False for __ in range(n)] for _ in range(n)]
        if i == 1:
            color_dic = {
                'R': 1,
                'G': 1,
                'B': 3,
            }
        for j in range(n):
            for k in range(n):
                if not visit[j][k]:
                    cnt += 1
                    dfs(j, k, graph[j][k])
        print(cnt)
    

  • 방문여부
    • 기존: visited로 4개 set으로 이루어진 dictionary 사용
    • 개선: 1개 사용
  • DFS 구성
    • 기존: 각 위치마다 4가지 경우 모두 탐색
    • 개선: 각 위치의 색에 따라 탐색 진행

---

참고문헌

-