[백준] 10026: 적록색약 python 구현 / BFS

첫 골드로 진입 ! 

문제

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

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

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

 

풀이

나는 그냥 color map을 만들어 사용하였다.

해당 색이면 1 아니면 0. 덕분에 시간 복잡도가 좀 올라갔을 것 같긴 하지만,,, 그냥 이렇게 구현

이렇게 하지 않으면 if문을 좀 더 자세히 줘야 할 듯?

 

그리고 추가로 이전 시간초과가 발생하였을 때 공부한게 여기서 나왔다 ! 

sys.stdin.readline() 함수는 개행문자를 포함하기 때문에 문자열 자체를 리스트로 쓰고 싶을 땐 strip()함수를 써줘야 한다. 안그러면 아래의 사태..

list(sys.stdin.readline())
# ['R', 'R', '\n']

list(sys.stdin.readline().strip())
# ['R', 'R']

 

CODE

import sys
from collections import deque

def bfs(sx, sy):
    queue = deque()
    queue.append((sx, sy))
    alpha_map[sx][sy] = 0

    # 방향 설정
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    while queue:
        now = queue.popleft()
        x, y = now

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # map 벗어나면 pass
            if nx<0 or ny<0 or nx>(n-1) or ny>(n-1): continue

            if alpha_map[nx][ny]:
                queue.append((nx, ny))
                alpha_map[nx][ny] = 0


n = int(input())
Map = []
for _ in range(n):
    Map.append(list(sys.stdin.readline().strip())) # readline함수는 개행문자('\n')을 포함하기에 strip()

# 적록색약 아닌 사람
color_cnt = 0
for alpha in ["R", "G", "B"]:
    alpha_map = [[1 if i==alpha else 0 for i in m] for m in Map]
    for i in range(n):
        for j in range(n):
            # 구역이면
            if alpha_map[i][j]:
                color_cnt += 1
                bfs(i, j)

# 적록색약인 사람
weak_cnt = 0
for alpha_list in [["R", "G"], ["B"]]:
    alpha_map = [[1 if i in alpha_list else 0 for i in m] for m in Map]
    for i in range(n):
        for j in range(n):
            # 구역이면
            if alpha_map[i][j]:
                weak_cnt += 1
                bfs(i, j)

print(color_cnt, weak_cnt)

 

깊이우선탐색(DFS) 분류를 풀고 있는데 어째서 BFS만 주구장창 쓰는진,,,ㅎㅎ