[Python] 백준 #10026- 적록색약

문제

---

10026번: 적록색약

코드

---

My answer (bfs 통과)

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

def bfs(x,y):
        Q=deque()
        Q.append((x,y))
        visit[x][y]=1
        while Q:
            x,y=Q.popleft()
            for i in range(4):
                n_x,n_y=x+direct[i][0],y+direct[i][1]
                if(0<=n_x<n and 0<=n_y<n):
                    if(visit[n_x][n_y]==0 and graph[n_x][n_y]==graph[x][y]):
                        visit[n_x][n_y]=1
                        Q.append((n_x,n_y))  
        return 0

n=int(input())
direct=[[1,0],[-1,0],[0,1],[0,-1]]
graph = [list(input()) for _ in range(n)]
answer=[]

visit=[[0]*n for _ in range(n)]
cnt=0
for i in range(n):
    for j in range(n):
        if(visit[i][j]==0):
            
            bfs(i,j)
            cnt+=1
answer.append(cnt)

visit=[[0]*n for _ in range(n)]
cnt=0

for i in range(n):
    for j in range(n):
        if graph[i][j]=='G':
            graph[i][j]='R'

for i in range(n):
    for j in range(n):
        if(visit[i][j]==0):
            bfs(i,j)
            cnt+=1
answer.append(cnt)

print(*answer)

import sys
from collections import deque

input = sys.stdin.readline

def mainS(t):
    global visit
    visit = [[0] * n for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0:
                if graph[i][j] in ['R','G'] and t == 1:
                    check=['R','G']
                else:check = [graph[i][j]]  
                bfs(i, j, check)
                cnt += 1
    return cnt

def bfs(x, y, check):
    Q = deque()
    Q.append((x, y))
    visit[x][y] = 1

    while Q:
        x, y = Q.popleft()
        for i in range(4):
            n_x, n_y = x + direct[i][0], y + direct[i][1]
            if 0 <= n_x < n and 0 <= n_y < n:
                if visit[n_x][n_y] == 0 and graph[n_x][n_y] in check:
                    visit[n_x][n_y] = 1
                    Q.append((n_x, n_y))

n = int(input())
direct = [[1, 0], [-1, 0], [0, 1], [0, -1]]
graph = [input().rstrip() for _ in range(n)]
answer = []

for i in range(2):
    answer.append(mainS(i))

print(answer[0], answer[1])

Another answer

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n = int(input().rstrip())
matrix = [list(input().rstrip()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

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

def dfs(x,y):
    visited[x][y] = True
    current_color = matrix[x][y]

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if (0 <= nx < n) and (0 <= ny < n):
            if visited[nx][ny]==False:
                if matrix[nx][ny] == current_color:
                    dfs(nx,ny)

for i in range(n):
    for j in range(n):
        if visited[i][j]==False:
            dfs(i,j)
            three_cnt += 1
for i in range(n):
    for j in range(n):
        if matrix[i][j]=='R':
            matrix[i][j]='G'

visited = [[False] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            dfs(i,j)
            two_cnt += 1

print(three_cnt,two_cnt)

풀이

---

우선 이 문제는 일반적인 그래프 탐색 문제에서 1혹은 0으로 갈수있는길 없는길을 확인하는걸 여기서는 단순히 R,G,B로 바꿔놓은 문제다. 우선 나는 2가지 방법으로 풀어봤다. (2가지 모두 bfs)

1. 단순하게 적록색맹이 아닌사람걸 계산하고, 그래프자체를 돌면서 R->G로 바꿔준 다음 적록색맹인 사람껄 계산하기. 이 때 visit을 초기화해주는 걸 잊지말기

2. 두번째 따로 계산하는것은 맞지만 코드를 좀 깔끔하게 쓰고 싶어서,(시간은 더 걸릴수도) 적록색맹자를 계산할 때 그래프를 따로 바꾸지않고 R과 G를 동일시하여 check라는 리스트에 넣고 in함수를 써서 해결해봤다~