코딩 챌린지 4일차 : 10026번 적록색약(G5)

이서진·2024년 9월 12일

DFS/BFS python 백준

눈높이 개발 코딩 챌린지 - 기본반B

목록 보기

4/13

10026 : 적록색약 - 문제 링크

1. 문제 탐색하기

입력

n 그림의 크기
paint[n][n] 그림

구하고자 하는 것

적록색약이 아닌 사람이 보는 구역 수 : DFS의 횟수
적록색약인 사람이 보는 구역 수 : R과 G를 구분하지 않고 진행했을 때의 DFS 횟수

알고리즘 설계

한 구역 내에 사방으로 연결된 요소를 찾기 위해 DFS 사용 (BFS도 무관)

두 사람이 보는 그림이 다르기 때문에 그래프도 두 개가 필요함
비적록색약 탐색 수행 후 그래프를 적록색약 그래프로 수정해서 사용

대신 방문 여부를 그래프 내용(-1)으로 확인할 수 없으니 visited 배열 생성 필요

주어진 그래프를 순회하며 DFS를 진행한 후 그 횟수를 세고 (적록색약 X)
R과 G를 하나의 문자로 치환하여 동일 작업을 반복 (적록색약 O)

시간복잡도

전체 그래프를 탐색, 사방 탐색, 총 2회 시행, 전체 그래프 복사
-> 4 $*$ 2 $*$ n $^2$ + n $^2$ -> $O(n^2)$
1 $\leq$ n $\leq$ 100이므로 최대 90,000번의 연산 수행 => 통과 가능

2. 코드 설계하기

import, 변수 선언, input 받기
그래프 순회
한 구역에 대해 DFS 수행

방문한 지점의 visited 값을 1로 변경

DFS 완료 시 count += 1
그래프 순회가 끝나면 G를 R로 치환하여 적록색약 그래프 생성
새 그래프에 대해 위의 작업 반복

같은 작업을 2번 수행하기 때문에 함수를 만들어서 진행
DFS를 함수로 만들 수도 있지만...
코드 중복이 싫어서 반복되는 부분 전체를 함수로 만듦

3. 시도 회차 수정 사항

1회차) 휴 살았다

4. 정답 코드

import sys
input = sys.stdin.readline

# 상하좌우 방향 배열
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

paint = []
visited = []


def count_zone():

    visited = [[0 for _ in range(n)] for _ in range(n)]
    count = 0

    for i in range(n):                      # y
        for j in range(n):                  # x
            if not visited[i][j]:
                visited[i][j] = 1
                count += 1
                # DFS
                stack = [[i, j]]
                while stack:
                    y, x = stack.pop()
                    # 사방 탐색
                    for k in range(4):
                        ny, nx = y + dy[k], x + dx[k]
                        # 그림 범위 내인지 확인
                        if -1 < ny < n and -1 < nx < n:
                            if not visited[ny][nx]:
                                if paint[ny][nx] == paint[y][x]:
                                    visited[ny][nx] = 1
                                    stack.append([ny, nx])
    
    return count


def main():
    
    # input 받기
    global n
    n = int(input())
    for _ in range(n):
        paint.append(input())

    # 비적록색약 그림 탐색
    normal = count_zone()

    # 적록색약 그림으로 수정
    for i in range(n):
        paint[i] = paint[i].replace("G", "R").rstrip()

    # 적록색약 그림 탐색
    weakness = count_zone()

    print(normal, weakness)

main()

문제를 보자마자 두 번 탐색하는 쉬운 방법(지금의 솔루션)이 떠올랐지만 그래도 골드 문제면 공식이 있겠지라고 생각하며 온갖 경우를 계산해본 나...

도저히 떠오르지 않아서 설마 두 번 탐색이 진짜 솔루션...? 하고 검색해보니 맞아서 좀 허탈했다😅 근데 막상 함수도 써보고 프로그램 작성하니 꽤 힘들었다. 골드 기분 탓인가... 함수랑 친해져야지 응응ㅇ...