[백준] 10026번 적록색약(python)

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

10026번: 적록색약

 

1. 내가 작성한 코드

from collections import deque

def bfs(matrix,i,j,cnt,visit):

  queue = deque()

  queue.append((i,j))

  visit[i][j] = cnt

  dx = [-1,1,0,0]
  dy = [0,0,-1,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
      
      if matrix[nx][ny] != matrix[x][y]:
        continue

      if matrix[nx][ny] == matrix[x][y] and visit[nx][ny] == 0:
        visit[nx][ny] = 1
        queue.append((nx,ny))


n = int(input())

matrix1 = [list(input()) for _ in range(n)] #적록색약x
matrix2 = [[0] * n for _ in range(n)] #적록색약o

for i in range(n): #적록색약인 경우 R,G를 같게 인식함
  for j in range(n):
    if matrix1[i][j] == "G":
      matrix2[i][j] = "R"
    else:
      matrix2[i][j] = matrix1[i][j]

cnt1 = 1 
cnt2 = 1

visit1 = [[0] * n for _ in range(n)]
visit2 = [[0] * n for _ in range(n)]

for i in range(n):
  for j in range(n):
    if visit1[i][j] == 0:  #적록색약이 아닌 경우 
      bfs(matrix1,i,j,cnt1,visit1)
      cnt1 += 1
    if visit2[i][j] == 0: #적록색약인 경우
      bfs(matrix2,i,j,cnt2,visit2)
      cnt2 += 1

print(cnt1-1,cnt2-1)

1. 적록색약이 없는 사람이 보는 그림이 담긴 matrix 만들기

 

2. 적록색약이 있는 사람이 보는 그림이 담긴 matrix 만들기

=> G인경우 R로 교체해서 만듦

 

3. 같은 색이면서 방문한 적 없는 경우 visit를 1로 바꾸고 queue 빌 때 까지 돌리기

 

 

matrix와 visit,cnt 등 적록색약인 경우와 아닌 경우 각자 다르게 변수를 처리했는데

 

적록색약이 아닌 경우의 그림 수를 구하고, 적록색약이 있는 경우의 그림 수를 구하면 matrix list를 다시 설정해줄 필요 없다.

 

 

 

2.수정 코드

from collections import deque

def bfs(i,j):

  queue = deque()
  queue.append((i,j))

  visit[i][j] = 1

  dx = [-1,1,0,0]
  dy = [0,0,-1,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
      
      if matrix[nx][ny] != matrix[x][y]:
        continue

      if matrix[nx][ny] == matrix[x][y] and visit[nx][ny] == 0:
        visit[nx][ny] = 1
        queue.append((nx,ny))


n = int(input())

matrix = [list(input()) for _ in range(n)] #적록색약x

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

for i in range(n):
  for j in range(n):
    if visit[i][j] == 0:  #적록색약이 아닌 경우 
      bfs(i,j)
      cnt1 += 1

for i in range(n): #적록색약인 경우 R,G를 같게 인식함
  for j in range(n):
    if matrix[i][j] == "G":
      matrix[i][j] = "R"
    
visit = [[0] * n for _ in range(n)]
cnt2 = 0

for i in range(n):
  for j in range(n):
    if visit[i][j] == 0:  #적록색약이 아닌 경우 
      bfs(i,j)
      cnt2 += 1

print(cnt1,cnt2)