백준 / 10026번 적록색약 (DFS,BFS) / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 10026번 적록색약

문제 사이트: https://www.acmicpc.net/problem/10026

10026번: 적록색약

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

50388

28969

22173

56.500%

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1 복사

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 복사

4 3

출처

Olympiad > USA Computing Olympiad > 2013-2014 Season > USACO March 2014 Contest > Bronze 3번

• 문제를 번역한 사람: baekjoon
• 어색한 표현을 찾은 사람: corea

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

나의 풀이 (첫번째 풀이 - 시간초과, DFS)

 

첫번째 정상인 사람의 시야에서 봤을 때 DFS 탐색 결과 총 영역을 알아낸 뒤,

적록색약이 보았을 때의 시야로 (빨강, 초록 -> 모두 빨강으로 처리)  DFS 탐색 결과 총 영역을 알아내었다.

import sys
sys.setrecursionlimit(1000000)
visited = []
type_1 = 0
type_2 = 1

def dfs(y,x,type_,m):
    global visited
    direct = [(1,0),(-1,0),(0,1),(0,-1)] # 상 하 좌 우
    if [y,x,type_] not in visited:
        visited.append([y,x,type_])
        for i in range(4):
            yy = y + direct[i][0]
            xx = x + direct[i][1]
            if 0 <= xx < n and 0 <= yy < n and m[yy][xx] == m[y][x]:
                dfs(yy,xx,type_,m)
    else:
        return

def search(n,m,type_):
    global visited
    cnt = 0
    for i in range(n):
        for j in range(n):
            if [i,j,type_] not in visited:
                dfs(i,j,type_,m)
                cnt += 1
    return cnt
if __name__ == "__main__":
    input = sys.stdin.readline

    n = int(input())

    maps = []
    for i in range(n):
        m = input().strip("\n")
        maps.append(list(m))
    
    cnt1 = search(n,maps,type_1)
    
    c_maps = list(maps) # 적록색약의 시야
    for i in range(len(c_maps)):
        for j in range(len(c_maps[i])):
            if c_maps[i][j] == "G":
                c_maps[i][j] = "R"
                
    cnt2 = search(n,c_maps,type_2)
    print(cnt1,cnt2)

 

두번째 풀이

방문처리하는 것을 

if not in 에서 3차원 리스트로 변경하여 해당 인덱스의 방문처리가 True 인지 False인지 검사하고, 

False 이면 해당 좌표를 방문하도록 하였다.

visited = [[False for _ in range(n)] for _ in range(n)] * 2
def dfs(y,x,type_,m):
    global visited
    direct = [(1,0),(-1,0),(0,1),(0,-1)] # 상 하 좌 우
    if visited[type_][i][j] == False :
        visited[type_][i][j] = True # 방문처리
        for i in range(4):
            yy = y + direct[i][0]
            xx = x + direct[i][1]
            if 0 <= xx < n and 0 <= yy < n and m[yy][xx] == m[y][x]:
                dfs(yy,xx,type_,m)
    else:
        return

해당 코드 처럼 수정하여서 아래에 최종코드로 제출함

 

import sys
sys.setrecursionlimit(1000000)
type_1 = 0 # 정상인 
type_2 = 1 # 적록색약 

def dfs(y,x,type_,m):
    global visited
    direct = [(1,0),(-1,0),(0,1),(0,-1)] # 상 하 좌 우
    if visited[type_][i][j] == False :
        visited[type_][i][j] = True # 방문처리
        for i in range(4):
            yy = y + direct[i][0]
            xx = x + direct[i][1]
            if 0 <= xx < n and 0 <= yy < n and m[yy][xx] == m[y][x]:
                dfs(yy,xx,type_,m)
    else:
        return

def search(n,m,type_):
    global visited
    cnt = 0
    for i in range(n):
        for j in range(n):
            if visited[type_][i][j] == False :
                dfs(i,j,type_,m)
                cnt += 1
    return cnt
if __name__ == "__main__":
    input = sys.stdin.readline

    n = int(input())
    visited = [[False for _ in range(n)] for _ in range(n)] * 2
    maps = []
    for i in range(n):
        m = input().strip("\n")
        maps.append(list(m))
    
    cnt1 = search(n,maps,type_1)
    
    c_maps = list(maps) # 적록색약의 시야
    for i in range(len(c_maps)):
        for j in range(len(c_maps[i])):
            if c_maps[i][j] == "G":
                c_maps[i][j] = "R"
                
    cnt2 = search(n,c_maps,type_2)
    print(cnt1,cnt2)

결론

1. 우선 적록색맹이 아닐 때 영역의 개수를 구한다.
2. R을 G로 바꿔준다.
3. 적록색맹일 때 영역의 개수를 구한다.

다른 풀이 (BFS)

from collections import deque

def BFS(x,y):
    q.append((x,y))
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    visited[x][y] = 1
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            # 인덱스 범위 안에 있으면서, 같은 색이면서, 방문 안한 경우
            if 0<=nx<N and 0<=ny<N and a[nx][ny] == a[x][y] and not visited[nx][ny]:
                visited[nx][ny] = 1  # 방문체크 후 큐에 넣음
                q.append((nx,ny))


N = int(input())
a = [list(input()) for _ in range(N)]
q = deque()

# 적록색약 아닌 경우
visited = [[0] * N for _ in range(N)]
cnt1 = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:  # 아직 방문 안한 경우만 체킹
            BFS(i,j)
            cnt1 += 1

# 적록색약인 경우
for i in range(N):
    for j in range(N):
        if a[i][j] == 'G':
            a[i][j] = 'R'

visited = [[0] * N for _ in range(N)]
cnt2 = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            BFS(i,j)
            cnt2 += 1

print(cnt1, cnt2)

---

※ 알아야 할 것

- sys.setrecursionlimit(1000000) :재귀 함수의 최대 깊이를 1000000으로 설정

- 방문처리는 1차원이 아닌 좌표값의 방문처리를 확인할 수 있도록 2차원이나 3차원으로 나타내는 것이 효율적 (인덱스 접근이므로)