[BOJ] 백준 10026 적록색약

태환·2024년 2월 3일
0

Coding Test

목록 보기
46/151

📌 [BOJ] 백준 10026 적록색약

📖 문제

📖 예제

📖 풀이

import sys
sys.setrecursionlimit(10000000)

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

N = int(input())
graph = []
for _ in range(N):
  graph.append(list(input()))

visited = [[0] * N for _ in range(N)]

def DFS(x,y):
  visited[x][y] = 1
  current = graph[x][y]
  for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    if 0<=nx<N and 0<=ny<N:
      if graph[nx][ny] == current and visited[nx][ny] == 0:
        DFS(nx,ny)

ans_1 = 0
for i in range(N):
  for j in range(N):
    if visited[i][j] == 0:
      DFS(i,j)
      ans_1 += 1

visited = [[0] * N for _ in range(N)]

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

ans_2 = 0
for i in range(N):
  for j in range(N):
    if visited[i][j] == 0:
      DFS(i,j)
      ans_2 += 1

print(ans_1, ans_2)

DFS/BFS 중 편한 방법을 통해 답을 출력할 수 있다.
우선 일반인이 인지하는 색으로 DFS 함수를 통해 몇개의 구역이 있는지 센다.
그리고 방문 기록을 0으로 초기화하고 입력 그래프의 'R'(or 'G')를 'G'(or'R')로 변환하여 통일해준 후 이전에 사용했던 DFS 함수를 통해 몇개의 구역이 있는지 센다.
그리고 두 경우를 모두 출력한다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글