[알고리즘/BFS&DFS] 10026번 : 적록색약 - python

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

 

 

---

• 문제
• 소요시간: 32분 30초

---

• 설계하기(접근방법) 

1. 입력받기

list 함수를 통해 문자열을 분할해주자

 

2. 구현하기

bfs를 2개 구현하면 된다.

 

1개는 정상적인 bfs

 

1개는 색약일때, RG를 함께 탐색하는 BFS를 제작하면 된다

 

3. 출력하기

각각 탐색 횟수를 count하여 출력한다.

 

 

---

• 코드(출력)

from collections import deque

n = int(input())

grid = []
visited = [[0 for _ in range(n)] for _ in range(n)]
visited_x = [[0 for _ in range(n)] for _ in range(n)]
o_cnt = 0
x_cnt = 0


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

for i in range(n):
    grid.append(list(input()))
    
# 정상
def bfs(a, b, color):
    q = deque()
    q.append([a,b])
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0 <= ny < n:
                if visited[nx][ny] == 0:
                    if grid[nx][ny] == color:
                        visited[nx][ny] = 1
                        q.append([nx,ny])
                        
# 색약
def bfs_x(a, b, color_1, color_2):
    q = deque()
    q.append([a,b])
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0 <= ny < n:
                if visited_x[nx][ny] == 0:
                    if grid[nx][ny] == color_1 or grid[nx][ny] == color_2:
                        visited_x[nx][ny] = 1
                        q.append([nx,ny])

# 정상
for i in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            visited[i][j] = 1
            bfs(i,j,grid[i][j])
            o_cnt += 1

# 색약
for i in range(n):
    for j in range(n):
        if visited_x[i][j] == 0:
            visited_x[i][j] = 1
            if grid[i][j] == 'R' or grid[i][j] == 'G':
                bfs_x(i,j,'R','G')
                x_cnt += 1
            else:
                bfs_x(i,j,'B,','B')
                x_cnt += 1



print(o_cnt, x_cnt)

---

• 얻어갈 부분

1. 함수 하나에 2가지 경우를 다 넣으려다가 오히려 가독성이 나빠졌다. 메모리가 모자란것도 아니니 쉽게쉽게 하자

2. bfs 범위 설정을 그리드의 길이로 해야하는데, xy 인자를 넣어서 오류가 났다. 다음에 주의하자