(Python/🥇5)백준알고리즘 10026번: 적록색약

백준알고리즘 적록색약

문제:

 

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

입력:

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄부터 N개 줄에는 그림이 주어진다.

출력:

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

 

import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


sys.setrecursionlimit(100000)
N = int(sys.stdin.readline())
map = [list(sys.stdin.readline().rstrip()) for i in range(N)]
visited = [[False] * N for _ in range(N)]



move = [(1,0),( -1,0),(0,-1),(0,1)] #상,하,좌,우
def dfs(x, y):
    now_color = map[x][y]
    visited[x][y] = True
    for dx,dy in move:
        nx = x + dx
        ny = y + dy
        if 0 <= nx <= N-1 and 0 <= ny <= N-1 and visited[nx][ny] == False:
            if now_color == map[nx][ny]: # 다음 색칠한 것과 같으면
                dfs(nx, ny)
tur = 0
for i in range(N):
    for j in range(N):
        if visited[i][j] ==False:
            dfs(i, j)
            tur += 1
print(tur, end = " ")

for i in range(N):
    for j in range(N):
        if map[i][j] == "G":
            map[i][j] = "R"
visited = [[False] * N for i in range(N)]

tur = 0
for i in range(N):
    for j in range(N):
        if visited[i][j] ==False:
            dfs(i, j)
            tur += 1
print(tur)

 

dfs 를 사용한다. 

 

참고 

bfs는 아래처럼 하면 된다.

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def bfs(x, y):
    visited[x][y] = 1
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        dxdy = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if -1 < nx < n and -1 < ny < n:
                if grid[nx][ny] == grid[x][y] and not visited[nx][ny]:
                    visited[nx][ny] = 1
                    q.append((nx, ny))

n = int(input())
grid = [list(map(str, input().strip())) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]

ncw = 0 #색약 x
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            ncw += 1
print(ncw, end=' ')

cw = 0 #색약
visited = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if grid[i][j] == 'R':
            grid[i][j] = 'G'

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            cw += 1
print(cw)

https://letalearns.tistory.com/148