[백준] 10026 적록색약

www.acmicpc.net/problem/10026

10026번: 적록색약

def dfs1(row, col, matrix,
         visited):
    delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우
    stack = [(row, col)]
    while stack:
        visit_node = stack[-1]
        visited[visit_node[0]][visit_node[1]] = 1
        adjacent = []
        for dt in delta:
            if 0 <= visit_node[0] + dt[0] < len(matrix) and 0 <= visit_node[1] + dt[1] < len(matrix):
                if matrix[visit_node[0]][visit_node[1]] == matrix[visit_node[0]+dt[0]][visit_node[1]+dt[1]]:
                    if not visited[visit_node[0]+dt[0]][visit_node[1]+dt[1]]:
                        adjacent.append((visit_node[0] + dt[0], visit_node[1] + dt[1]))
        for adj in adjacent:
            stack.append(adj)
            break
        else:
            stack.pop()


def dfs2(row, col, matrix, visited):
    delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우
    stack = [(row, col)]
    while stack:
        visit_node = stack[-1]
        visited[visit_node[0]][visit_node[1]] = 1
        adjacent = []
        for dt in delta:
            if 0 <= visit_node[0] + dt[0] < len(matrix) and 0 <= visit_node[1] + dt[1] < len(matrix):
                if matrix[visit_node[0]][visit_node[1]] == matrix[visit_node[0] + dt[0]][visit_node[1] + dt[1]]:
                    if not visited[visit_node[0] + dt[0]][visit_node[1] + dt[1]]:
                        adjacent.append((visit_node[0] + dt[0], visit_node[1] + dt[1]))
                elif matrix[visit_node[0]][visit_node[1]] == 'R' and matrix[visit_node[0] + dt[0]][visit_node[1] + dt[1]] == "G":
                    if not visited[visit_node[0] + dt[0]][visit_node[1] + dt[1]]:
                        adjacent.append((visit_node[0] + dt[0], visit_node[1] + dt[1]))
                elif matrix[visit_node[0]][visit_node[1]] == 'G' and matrix[visit_node[0] + dt[0]][visit_node[1] + dt[1]] == "R":
                    if not visited[visit_node[0] + dt[0]][visit_node[1] + dt[1]]:
                        adjacent.append((visit_node[0] + dt[0], visit_node[1] + dt[1]))
        for adj in adjacent:
            stack.append(adj)
            break
        else:
            stack.pop()


n = int(input())
picture = [input() for _ in range(n)]

visited1 = [[0]*n for _ in range(n)]
visited2 = [[0]*n for _ in range(n)]
result1 = 0   # 정상인
result2 = 0  # 적녹색약

for i in range(n):
    for j in range(n):
        # 정상
        if not visited1[i][j]:
            dfs1(i, j, picture, visited1)
            result1 += 1

        # 적녹색약
        if not visited2[i][j]:
            dfs2(i, j, picture, visited2)
            result2 += 1


print(result1, result2)

처음에 든 생각은 BFS로 짜면 조금더 나을것같다고는 생각했다.

하지만 아직 queue에 대해서 안배웠기도 했고 아직 DFS도 제대로 못짜서 일부러 DFS로 짰다.

BFS로 구현하라고 하면 할수는 있다.

from collections import deque에 stack = []대신 q = deque()로 선언한후 leftpop()으로 break없이 돌리면 된다.

어찌되었든 DFS 로 짜긴했는데 코드가 많이 더럽다.

dfs1 함수는 같은 색깔일때만 도는 코드이고, dfs2 함수는 dfs1에 R,G의 조건을 단 코드이다.

델타로 도는 부분들은 모두 인접 정점들을 찾는 경우이고, 방문하지 않은 인접 정점들만 배열에 추가했다.

다음에는 재귀로 구하는 방법을 사용해야겠다.

---

import sys
sys.setrecursionlimit(10000)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
normal = {'R': 3, 'B': 2, 'G': 1}
weak = {'R': 2, 'B': 1, 'G': 2}

def dfs(x, y, visited, status):
    visited[x][y] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and status[grid[x][y]] == status[grid[nx][ny]] and not visited[nx][ny]:
            dfs(nx, ny, visited, status)

n = int(input())
grid = [input() for _ in range(n)]
visited1 = [[False]*n for _ in range(n)]
visited2 = [[False]*n for _ in range(n)]
count1, count2 = 0, 0
for i in range(n):
    for j in range(n):
        if not visited1[i][j]:
            dfs(i, j, visited1, normal)
            count1 += 1
        if not visited2[i][j]:
            dfs(i, j, visited2, weak)
            count2 += 1
print(count1, count2)

타인의 코드인데 공부하기위해 가져왔다.

적록색약을 구분하기 위해 dictionary를 사용하였다. 좋은방법같다.

재귀를 썼을때 조금더 간결하고 보기쉽다. 그런데 재귀 깊이가 있어서 에러에 걸리나보다.