백준 10026번(적록색약) 파이썬

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

10026번: 적록색약

이번 문제는 무려 '골드' 문제다... 처음으로 골드 문제를 풀어보았다. 개인적으로 놀란것은 풀만했단 것이다.

그래프 탐색 문제를 풀면서 느끼는 거지만 진짜 문제들의 큰 틀은 다른게 없다. 정말로 접근은 비슷하고 추가하는 조건만 조금 수정해주면 된다. 심지어 이 조건이 그렇게 어려운것도 아니다. if문 하나 수정해주면 모든 문제들이 풀린다.

BFS,DFS 더 이상 쫄지 않아도 된다!!

아래 코드 주석에 설명을 달아놨다.

 

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

graph = []
visited = [[False]*(N) for _ in range(N)] # 방문 리스트 선언

dx=[1,-1,0,0] # 상하좌우
dy=[0,0,1,-1]

for _ in range(N):
    graph.append(list(input().rstrip())) # 그래프에 입력값 추가
    
def bfs(a,b,color):
    
    q=deque()
    q.append((a,b))
    
    while q:
        x,y=q.popleft()
        
        if visited[x][y] == False: #미방문일 경우
            visited[x][y] = True #방문처리 해준다
            for i in range(4): # 상하좌우 탐색
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<N and graph[nx][ny] == color: # 벽이나 범위 밖을 넘지 않고 색깔이 같다면
                    q.append((nx,ny)) # 데크에 바뀐 좌표를 추가

#적록색약이 아닐때
cnt=0
for i in range(N):
    for j in range(N):
        if visited[i][j] == False:
            color = graph[i][j] # 현재 위치의 색깔을 color 선언
            bfs(i,j,color)
            cnt+=1 #색깔 구역 카운트
print(cnt, end=" ")


#적록색약일때
visited = [[False]*(N) for _ in range(N)] # 적록색약일때 방문리스트 재선언
for i in range(N):
    for j in range(N):
        if graph[i][j] =='R': # R과G를 동일하게 변경 
            graph[i][j] = 'G'
        
#아래는 적록색약이 아닐때 설명과 동일
cnt_bg=0
for i in range(N):
    for j in range(N):
        if visited[i][j] == False:
            color = graph[i][j]
            bfs(i,j,color)
            cnt_bg+=1
print(cnt_bg)

할만 했다.

내가 골드문제가 할만 했다니 진짜 성장한거 같다.

그래프 탐색 문제 다 풀어버려야겠다.