[알고리즘 풀이] 적록색약(10026)

1. 문제 설명

[적록색약]

문제

입력

출력

예제 입출력

풀이 및 접근

 입력으로 주어진 배열에서 상하좌우로 같은 색상끼리 그래프로 연결하여 생성되는 그래프의 개수를 세는 문제이다. 내가 작성한 코드는 아래와 같다.

코드

import sys
from collections import deque

shift_pattern = [(1, 0), (-1, 0), (0, -1), (0, 1)]

def bfs(picture, visited):
    area_cnt = 0
    i = 0
    while i < N:
        j = 0
        while j < N:
            if visited[i][j] == False:
                cur_color = picture[i][j]

                visited[i][j] = True
                que.append((i, j, area_cnt))
                while que:
                    y, x, _ = que.popleft()
                    for shift in shift_pattern:
                        dy = y + shift[0]
                        dx = x + shift[1]
                        if 0 <= dy < N  and 0 <= dx < N and visited[dy][dx] == False and picture[dy][dx] == cur_color:
                            que.append((dy, dx, area_cnt))
                            visited[dy][dx] = True
                area_cnt += 1
            j += 1
        i += 1
    return area_cnt

N = int(sys.stdin.readline().rstrip())
que = deque()
visited = [[False for _ in range(N)] for _ in range(N)]

picture = []
for _ in range(N):
    picture.append(list(sys.stdin.readline().rstrip()))

print(bfs(picture, visited))

que = deque()
visited = [[False for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in range(N):
        if picture[i][j] == 'G':
            picture[i][j] = 'R'
print(bfs(picture, visited))

접근

처음 내 접근 방식은 아래와 같다.

1. 이미 방문한 곳인지 확인하기 위해 visited 배열을 사용하자
2. visited가 False인 곳을 방문한 경우, 상하좌우 중 현재와 같은 색깔이 곳을 Queue에 넣고 탐색하자. 탐색한 곳은 visited를 True로 변경한다.
3. visited가 False인 곳을 순차적으로 방문하자.
4. Queue에 넣을 때 좌표뿐만 아니라 현재 탐색된 연결그래프(구역)의 개수도 넣어주어 현재까지 몇개의 구역이 탐색되었는지 확인하자

위의 방법을 사용하면, 정상인이 보는 구역의 개수를 찾을 수 있었다.

이 다음에는 적록색약이 보는 구역을 개수를 찾아야하는데 이 과정에서 어렵게 생각하여 시간이 소요되었다.
그 이유는 실행시간을 의식하여 탐색 한번에 정상인과 적록색약이 보는 구역의 개수를 모두 구해야된다고 생각했기때문이다.😂
단순하게 picture의 R을 G로 바꾸고 다시 한번 탐색을 하는 방식으로 코드를 작성하니 통과되었다.

회고

• BFS가 아니라 DFS로 풀어도 되었을것 같다.
  그래프 문제는 경험상 DFS로 풀면 시간초과가 걸리는 경향이 있어 습관적으로 BFS로 풀게 되는 것 같다. 처음 직관적으로 생각한대로 BFS로 풀었지만 문제 구조상 DFS로 풀었으면 더 쉽게 풀렸을 것 같다. 또한, 문제조건이 1 <= N <= 100 이라 DFS 풀이에서도 비교적 시간제한에서 여유로운 문제였던것 같다.

• 입력 조건을 체크하는 습관이 필요할 것 같다.
  위에서 이어지는 말이지만 이번 문제의 경우 1 <= N <= 100으로 비교적 입력 스케일이 작은편이었다. 입력 스케일이 큰 경우 2차원 배열을 모두 탐색하는 것 조차 불가능한 문제들이 대부분인데, 이 문제의 경우 최대 입력 스케일이 100*100 배열이기 때문에 배열을 탐색하는게 자유롭다는 것을 입력 조건을 보고 더 빨리 알아차렸으면 문제 풀기가 더 수월햇을 것 같다.