[ 2023-07-24 🪽 TIL ]

백준 10026, 4963번 파이썬

10026번

문제

---

코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
color = []
result_1 = []
for _ in range(n):
  color.append(list(input().strip()))

visted_1 = [[False] * n for _ in range(n)] 
# 색약 없는 사람의 방문기록
visted_2 = [[False] * n for _ in range(n)]
# 색약 있는 사람의 방문기록
move = ((0,1), (0, -1), (1, 0), (-1, 0)) # (좌, 우, 하, 상)
cnt_1, cnt_2 = 0, 0

for i in range(n):
  for j in range(n):
    if (not visted_1[i][j]):
      cnt_1 += 1
      c = color[i][j]
      q = deque([(i,j)])
      visted_1[i][j] = True
      
      while q: # bfs
        ci, cj = q.popleft()
        
        for mi, mj in move:
          xi,xj = (ci + mi), (cj + mj)
          if (0<=xi<n) and (0<=xj<n) and (not visted_1[xi][xj]) and color[xi][xj] == c: 
          # n x m 범위 안 상하좌우 내에 방문하지 않은 곳 중에 
          # 같은 색을 가진 부분이 있는지 체크
            q.append((xi,xj))
            visted_1[xi][xj] = True
            
umm = ('R', 'G') # 색약인에게는 R과 G가 동일 경로로 체크된다. 

for i in range(n):
  for j in range(n):
    if (not visted_2[i][j]):
      cnt_2 += 1
      c = color[i][j]
      q = deque([(i,j)])
      visted_2[i][j] = True
      
      while q: # bfs
        ci, cj = q.popleft()
        
        for mi, mj in move:
          xi,xj = (ci + mi), (cj + mj)
          if (0<=xi<n) and (0<=xj<n) and (not visted_2[xi][xj]) :
            if (c in umm): # R 또는 G인 경우
            # 다음 경로에 R or G가 오면 이동 가능하다. 
              if (color[xi][xj] in umm): 
                q.append((xi,xj))
                visted_2[xi][xj] = True
            elif color[xi][xj] == c: # B 일때 
              q.append((xi,xj))
              visted_2[xi][xj] = True

print(cnt_1, cnt_2)

4963번

문제

---

코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
result = []
move = ((0,1), (1,0), (-1, 0), (0, -1), (1,1), (1, -1), (-1, -1), (-1, 1)) 
# 상하좌우 말고 대각선으로도 이동가능

while n > 0 and m > 0: # n, m이 둘 다 0이 입력으로 들어오면 끝난다.
  feild = []
  visited = [[0] * n for _ in range(m)]
  count = 0
  
  for _ in range(m):
    feild.append(list(map(int, input().strip().split())))

  for i in range(m):
    for j in range(n):
      if visited[i][j] == 0 and feild[i][j] == 1:
        count += 1
        
        q = deque([(i, j)])
        visited[i][j] = 1
        
        while q : # bfs
          ci, cj = q.popleft()
          
          for mi, mj in move :
            xi, xj = (mi + ci), (mj + cj)
            if 0<=xi<m and 0<=xj<n and visited[xi][xj] == 0 and feild[xi][xj] == 1:
            # 이동가능 범위 내에 방문한적 없으면서 조건에 만족하는 경우
            # 이동가능 섬으로 간주한다.
              q.append((xi, xj))
              visited[xi][xj] = 1
              
  result.append(count)
  n, m = map(int, input().split())
  
for val in result:
  print(val)

두 문제 모두 bfs로 해결하였습니다.
bfs가 아무래도 구현하기 더 쉬운 것 같습니다.