10026. [Python]적록색약

1. 문제

 

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

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 깊이 우선 탐색

 

3. 파이썬 코드

 

def DFS(start, flag):
    # DFS 진행
    global count
    stack = [start]
    # 초기값 선언
    visited[start[0]][start[1]] = True
    while stack:
        y,x = stack.pop()
        # 방향 배열 탐색
        for k in range(4):
            ny = y + direction[k][0]
            nx = x + direction[k][1]
            # 범위내 존재 시
            if 0 <= ny < N and 0 <= nx < N:
                # flag 변수를 통해 적녹색약 체크
                if flag == 0:
                    if not visited[ny][nx] and matrix[ny][nx] == matrix[y][x]:
                        stack.append((ny,nx))
                        visited[ny][nx] = True
                # 적록색약의 경우
                else:
                    # 방문하지 않았을때 R 값이 들어오면 matrix 값이 같거나 G 인 경우 스택 추가 후 방문 처리
                    if not visited[ny][nx]:
                        if matrix[y][x] == "R":
                            if matrix[ny][nx] == "G" or matrix[ny][nx] == matrix[y][x]:
                                stack.append((ny,nx))
                                visited[ny][nx] = True
                        # G가 들어온 경우 값이 같거나 R인 경우
                        elif matrix[y][x] == "G":
                            if matrix[ny][nx] == "R" or matrix[ny][nx] == matrix[y][x]:
                                stack.append((ny,nx))
                                visited[ny][nx] = True
                        # 외의 경우 스택에 그대로 추가
                        else:
                            if not visited[ny][nx] and matrix[ny][nx] == matrix[y][x]:
                                stack.append((ny,nx))
                                visited[ny][nx] = True
    count += 1

N = int(input())

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

matrix = [ list(map(str,input())) for _ in range(N) ]

count = 0

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

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            DFS((i,j),0)
ans = count

count = 0
visited = [[False] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            DFS((i,j),1)

print(ans, count)

 

4. 문제를 풀고난 후 생각

 

• DFS(깊이 우선 탐색)을 할 수 있는지 물어보는 문제....
• "R" 값이 들어왔을 때 "G" 값이 근처에 있는지 방향배열을 탐색하며 확인을 하고, DFS를 두번 반복하여 일반 사람의 시선에서 본 영역과 적록색약의 시선에서 본 영역을 체크해주면 된다.
• DFS를 진행하며 끝날때 마다 count를 체크해줘서 영역의 개수를 구함.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 깊이 우선 탐색