백준 - 10026번 적록색약 python 문제풀이 [Hellfer]

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

10026번: 적록색약

🔷 알고리즘 분류 - BFS(너비우선탐색),  깊이우선탐색(DFS) , 난이도 - 골드 5

 

너비 우선 탐색(Breadth-First Search, BFS) 알고리즘은 그래프 또는 트리를 탐색하는 방법 중 하나로, 시작 노드에서 가장 가까운 노드부터 탐색하는 방법입니다. BFS는 '레벨(level)'이 같은 노드들을 모두 탐색한 후에 다음 레벨의 노드들을 탐색하게 됩니다.

BFS는 큐(Queue) 자료구조를 이용해서 구현됩니다. 큐는 '선입선출(FIFO, First-In-First-Out)'의 특성을 가지므로, 먼저 들어간 노드가 먼저 나오게 됩니다. 이 특성을 이용하여 BFS는 시작 노드부터 가까운 노드를 먼저 탐색하는 방식을 구현하게 됩니다.

다음은 BFS 알고리즘의 기본적인 순서입니다:

1. 시작 노드를 큐에 넣고 방문 처리를 합니다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문 처리를 합니다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

BFS는 최단 경로 문제에서 많이 사용되며, 또한 네트워크에서 가장 가까운 노드를 찾는 등의 문제에서도 사용됩니다. 이는 BFS가 시작 노드에서 가장 가까운 노드부터 탐색하기 때문입니다. 하지만 BFS는 모든 간선의 비용이 동일할 때만 최단 경로를 보장하므로, 간선의 비용이 다른 경우에는 다른 알고리즘(예: 다익스트라 알고리즘)을 사용해야 합니다.

🔶첫 번째 문제 풀이 - BFS(너비우선탐색)을 이용한 풀이

 

import sys
from collections import deque
input = sys.stdin.readline
dx=[0,0,-1,1]
dy=[-1,1,0,0]

# 너비 우선 탐색(Breadth-First Search) 함수 정의
def bfs(x,y):
    queue=deque()
    queue.append((x,y))
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            # nx와 ny가 그래프 범위 내에 있을 때
            if 0<=nx<n and 0<=ny<n :
                # 현재 노드와 인접 노드의 값이 같고, 인접 노드가 방문한 적 없을 때
                if graph[nx][ny]==graph[x][y] and not visited[nx][ny]:
                    queue.append((nx,ny))
                    visited[nx][ny]=True

n=int(input())  # 그래프 크기 입력 받기
graph=[list(input().strip()) for i in range(n)]  # 그래프 정보 입력 받기
visited=[[False]*n for i in range(n)]  # 방문 여부 저장 리스트 초기화
res1=0  # 첫 번째 결과값 초기화
for i in range(n):
    for j in range(n):
        # 아직 방문하지 않은 노드일 경우
        if not visited[i][j]:
            bfs(i,j)  # BFS 수행
            res1+=1  # 구역 개수 카운트

# 그래프에서 'G'를 'R'로 변경
for i in range(n):
    for j in range(n):
        if graph[i][j]=='G':
            graph[i][j]='R'

visited=[[False]*n for i in range(n)]  # 방문 여부 저장 리스트 초기화
res2=0  # 두 번째 결과값 초기화
for i in range(n):
    for j in range(n):
        # 아직 방문하지 않은 노드일 경우
        if not visited[i][j]:
            bfs(i,j)  # BFS 수행
            res2+=1  # 구역 개수 카운트

# 두 결과값 출력
print(res1,res2)

🔶두 번째 문제 풀이 - 깊이우선탐색(DFS)을 이용한 풀이

 

import sys
sys.setrecursionlimit(10**6)  # 파이썬 재귀 깊이 제한을 늘림

dx = [-1, 1, 0, 0]  # x축 이동 방향
dy = [0, 0, -1, 1]  # y축 이동 방향

# 깊이 우선 탐색(DFS) 함수 정의
def dfs(x, y, arr, visited):
    visited[x][y] = True  # 현재 노드를 방문 처리
    color = arr[x][y]  # 현재 노드의 색상
    
    # 상하좌우로 이동
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        # 그래프 범위 안에 있고, 아직 방문하지 않은 노드이며, 같은 색상일 경우
        if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and arr[nx][ny] == color:
            dfs(nx, ny, arr, visited)  # 해당 노드로 이동

n = int(input())  # 그래프 크기 입력 받기
graph = [list(input()) for _ in range(n)]  # 그래프 정보 입력 받기
color_blind = [[i if i == 'B' else 'R' for i in row] for row in graph]  # 적록색약인 경우를 위해 'G'를 'R'로 변경

visited1 = [[False]*n for _ in range(n)]  # 적록색약이 아닌 경우를 위한 방문 여부 저장 리스트 초기화
visited2 = [[False]*n for _ in range(n)]  # 적록색약인 경우를 위한 방문 여부 저장 리스트 초기화

res1 = res2 = 0  # 결과값 초기화

# 그래프의 모든 노드를 확인
for i in range(n):
    for j in range(n):
        # 적록색약이 아닌 경우
        if not visited1[i][j]:
            dfs(i, j, graph, visited1)  # DFS 수행
            res1 += 1  # 구역 개수 카운트
        # 적록색약인 경우
        if not visited2[i][j]:
            dfs(i, j, color_blind, visited2)  # DFS 수행
            res2 += 1  # 구역 개수 카운트

print(res1, res2)  # 두 결과값 출력

🔶 초보자를 위한 생각주머니 키우기

🔸문제요약

이 문제는 적록색약 문제로 알려져 있습니다. 이 문제에서는 N x N 크기의 그리드가 주어지며, 각 칸은 'R'(빨강), 'G'(초록), 'B'(파랑) 중 하나로 채워져 있습니다. 이때, 인접한 같은 색상의 칸들을 모두 연결하여 구역을 정의합니다.

문제의 목표는 두 가지입니다:
1. 적록색약이 아닌 사람이 보았을 때의 구역의 개수를 구하고,
2. 적록색약인 사람이 보았을 때의 구역의 개수를 구합니다.

적록색약인 사람은 빨강과 초록을 구분할 수 없으므로, 이들을 같은 색상으로 보아야 합니다.

🔸해결전략

1. 이 문제는 BFS(너비 우선 탐색) 혹은 DFS(깊이 우선 탐색)를 이용하여 해결할 수 있습니다.

2. 먼저 적록색약이 아닌 사람이 보았을 때의 구역 개수를 구합니다. 각 구역의 시작점(아직 방문하지 않은 칸)에서 BFS나 DFS를 시작하고, 방문한 칸을 표시하면서 같은 색상의 칸만 방문하도록 합니다. 이렇게 해서 모 든 칸을 방문할 때까지 반복하고, BFS나 DFS를 시작한 횟수가 구역의 개수가 됩니다.

3. 그다음 적록색약인 사람이 보았을 때의 구역 개수를 구합니다. 이때는 빨강과 초록을 같은 색상으로 보아야 하므로, BFS나 DFS를 할 때 빨강과 초록을 같은 색상으로 처리하면 됩니다.

4. 최종적으로 적록색약이 아닌 사람이 보았을 때의 구역 개수와 적록색약인 사람이 보았을 때의 구역 개수를 출력합니다.

 

 

🤗파이팅입니다~ 여러분!!🤗