[Algorithm] 백준 10026 - 적녹색약 in Python(파이썬)

💡 백준 10026:

DFS 탐색

🌱 코드 in Python

알고리즘: DFS

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
g = []
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
ret = 0
ret_rg = 0

for i in range(n):
  g.append(list(map(str, input().strip())))

def dfs(cx, cy, c):
    visit[cx][cy] = 1
    for x, y in zip(dx, dy):
        nx = cx + x
        ny = cy + y
        if 0 <= nx < n and 0 <= ny < n:
            if visit[nx][ny] == 0 and g[nx][ny] == c:
                dfs(nx, ny, c)

visit = [[0] * n for _ in range(n)]
for i in range(n): # 적녹색약이 아닌 경우
    for j in range(n):
        if visit[i][j] == 0:
            dfs(i, j, g[i][j])
            ret += 1

for i in range(n): # 적녹색약용 그래프 치환
    for j in range(n):
        if g[i][j] == 'G':
            g[i][j] = 'R'

visit = [[0] * n for _ in range(n)] # visit배열 초기화
for i in range(n): # 적녹색약인 경우
    for j in range(n):
        if visit[i][j] == 0:
            dfs(i, j, g[i][j])
            ret_rg += 1

print(ret, ret_rg)

이번 문제는 적녹색약인 경우와 아닌 경우의 구역의 수를 다르게 책정하는 문제였다

나는 벽 부수고 이동하기 문제와 같이 한 반복문 안에서 두가지 경우의 수를 구하는 방법을 구현하고 싶었지만..
내 머리로 떠오르지 않아 그냥 일단 냅다 풀고 G를 R로 바꿔서 한 번 더 돌리자! 로 일단 풀어보았다
시간초과가 날 것 같아서 일단 내가 풀 수 있는 방법으로 먼저 풀고 다른 방법을 찾아보기로 했기 때문

근데 넘나 다행인 것은~! 시간초과가... 아니었습니다!
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

다행이얌 ㅎㅎㅎㅎㅎㅎㅎ

에휴 이게 다행이 아니라 예상한 결과여야 하는데 ㅠㅠ

아무래도 입력의 수가 100 * 100이라서.. 그랬나보다..

🧠 기억하자

1. 한 반복문 안에서 끝내는 방법이 있을지도 몰라~!

백준 10026 바로가기