백준 10026 적록색약 Python 3

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

10026번: 적록색약

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ10026.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
sys.setrecursionlimit(20000)
input = sys.stdin.readline
def dfs(x, y, color):
    for ddx, ddy in zip(dx, dy):
        nx = x+ddx
        ny = y+ddy
        if 0 <= nx < N and 0 <= ny < N and picture[ny][nx] == color and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny, color)

def blind_dfs(x, y, color):
    for ddx, ddy in zip(dx, dy):
        nx = x+ddx
        ny = y+ddy
        if 0 <= nx < N and 0 <= ny < N and not visit[ny][nx]:
            if (color == picture[ny][nx]) or (color == 'R' and picture[ny][nx] == 'G') or (color == 'G' and picture[ny][nx] == 'R'):
                visit[ny][nx] = 1
                blind_dfs(nx, ny, color)

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

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

normal_area = 0
visit = [[0]*N for _ in range(N)]
for y in range(N):
    for x in range(N):
        if not visit[y][x]:
            visit[y][x] = 1
            dfs(x, y, picture[y][x])
            normal_area += 1

blind_area = 0
visit = [[0]*N for _ in range(N)]
for y in range(N):
    for x in range(N):
        if not visit[y][x]:
            visit[y][x] = 1
            blind_dfs(x, y, picture[y][x])
            blind_area += 1
print(normal_area, blind_area)

---

풀이 과정

풀이 시간 22분

import sys
#최대 100x100 그래프를 탐색해야하므로 재귀 제한을 늘린다
sys.setrecursionlimit(20000)
input = sys.stdin.readline

#일반 사람의 탐색 알고리즘
def dfs(x, y, color):
	#인접한 4방향 탐색
    for ddx, ddy in zip(dx, dy):
        nx = x+ddx
        ny = y+ddy
        #범위 내에 있으면서, 같은 색이 있는 칸이고 이전에 방문한 적 없다면 탐색한다
        if 0 <= nx < N and 0 <= ny < N and picture[ny][nx] == color and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny, color)

#적록색약인 사람의 탐색 알고리즘
def blind_dfs(x, y, color):
	#인접한 4방향 탐색
    for ddx, ddy in zip(dx, dy):
        nx = x+ddx
        ny = y+ddy
        
        #범위 내에 있으면서 이전에 방문한 적 없는 경우
        if 0 <= nx < N and 0 <= ny < N and not visit[ny][nx]:
        	#같은 색이 있는 칸이거나, 첫번째 칸이 빨간색이고 (nx, ny)칸이 초록색이거나, 첫번째 칸이 초록색이고 (nx, ny)칸이 빨간색인 경우, 탐색을 이어간다
            if (color == picture[ny][nx]) or (color == 'R' and picture[ny][nx] == 'G') or (color == 'G' and picture[ny][nx] == 'R'):
                visit[ny][nx] = 1
                blind_dfs(nx, ny, color)

#입력 받아오기
N = int(input())
picture = []
for _ in range(N):
    picture.append(list(input().rstrip()))

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

#적록색약이 아닌 사람이 봤을 때 구역의 수 구하기
normal_area = 0
visit = [[0]*N for _ in range(N)]
for y in range(N):
    for x in range(N):
    	#이전에 방문한 적이 없는 경우, 새로운 영역을 탐색한다
        if not visit[y][x]:
            visit[y][x] = 1
            dfs(x, y, picture[y][x])
            #구역의 수 카운팅
            normal_area += 1
            
#적록색약인 사람이 봤을 때 구역의 수 구하기
blind_area = 0
visit = [[0]*N for _ in range(N)]
for y in range(N):
    for x in range(N):
        if not visit[y][x]:
            visit[y][x] = 1
            blind_dfs(x, y, picture[y][x])
            #구역의 수 카운팅
            blind_area += 1
            
print(normal_area, blind_area)

#시간복잡도 = O(V+E), 공간복잡도 = O(n)