🥇[백준] 10026 적록색약 (골드5) / BFS

문제요약

나의 코드 및 설명

• RGB를 012로 변환. 지금 생각해보니 for _ in ("R","G,","B")로 하면 되지 않았을까 싶다.
• 0,1,2 돌면서 적록색약 아닌 사람 먼저 카운트
• 그리드 중 R,G(0,1)을 같게 만든다.
• G,B(1,2) 돌면서 적록색약인 사람 카운트

from collections import deque

def bfs(sx,sy,color,v):
    queue = deque()
    queue.append((sx,sy))
    v[sy][sx] = 1
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=n:
                continue
            else:
                if board[ny][nx] == color and v[ny][nx] == 0:
                    v[ny][nx] = 1
                    queue.append((nx,ny))

n = int(input())

board = []

#R,G,B를 각각 0,1,2로 바꿔준다.
for _ in range(n):
    string = list(input())
    temp_list = []
    for i in string:
        if i == "R":
            temp_list.append(0)
        elif i == "G":
            temp_list.append(1)
        elif i == "B":
            temp_list.append(2)
    board.append(temp_list)

dx = [0,1,0,-1]
dy = [-1,0,1,0]

visited = [[0] * n for _ in range(n)] #적록색약 아닌사람 방문 테이블
rg_visited = [[0] * n for _ in range(n)] #적록색약인 사람 방문 테이블

cnt = 0 #적록색약 아닌사람
rg_cnt = 0 #적록색약인 사람

#적록색약 아닌사람 먼저 카운트
for rgb in range(3): #R,G,B 돌아가며 확인
    for i in range(n):
        for j in range(n):
            if board[i][j] == rgb and visited[i][j] == 0: #아직 방문 안했다면
                bfs(j,i,rgb,visited) #bfs수행 (이때, rgb정보와 방문테이블을 변수로 하여 호출한다.)
                cnt += 1

#적록색약 아닌사람 카운트 끝났으니 이제 적록색약인 사람 카운트 할 차례
#R,G 값을 같게 만든다.
for i in range(n):
    for j in range(n):
        if board[i][j] == 0:
            board[i][j] = 1

#적록색약인 사람 카운트
for rgb in range(1,3):
    for i in range(n):
        for j in range(n):
            if board[i][j] == rgb and rg_visited[i][j] == 0:
                bfs(j,i,rgb,rg_visited)
                rg_cnt += 1

print(cnt, rg_cnt)

 

피드백

처음 문제를 보고 시간복잡도와 메모리를 줄여서 문제를 구현해봐야 될 것 같다는 생각이 들었고, 적록색약이 아닌 사람과, 적록색약인 사람의 그리드를 따로 만들지 않고 한 번에 해결하는 방법과, bfs 함수를 하나만 작성하는 방법을 찾기 위해 고민했다. 사실 제출할 때도 시간, 메모리 초과 등의 에러가 뜰까봐 걱정했는데 다행히 92ms로 맞았다는 판정을 받았다. 구글링을 통해 다른 사람이 고민한 흔적들을 보니까 그리드를 두 개 만들면 메모리 초과가 발생하는 모양이다. 다른 사람들이 작성한 코드를 보고 배울 수 있었던 점은, 나의 코드는 bfs 함수의 변수에 RGB를 줌으로써 3중 for문을 통해 각기 다른 RGB 값의 bfs를 호출했는데, 다른 사람들은 bfs 함수 내에서 현재 좌표와 다음 좌표가 같을 경우(if board[ny][nx] == board[y][x] ~) 큐에 넣어주는 식으로 문제를 풀이하였다. 이렇게 할 경우 3중 for문을 사용하지 않아도 돼서 코드가 더 간결하다.