10026 적록색약

문제 분석

1. 아이디어
- 인접한 픽셀의 색이 같은 경우 dfs
- 방문하지 않은 노드에 대하여 dfs 반복하여 모든 그룹 카운팅
- 적록색맹의 경우 R,G를 통일하여 같은 방식으로 그룹 탐색

2. 복잡도
- O(n*2)

3. 자료구조
- 재귀, 리스트

해결 코드

import sys
sys.setrecursionlimit(10 ** 6) # 재귀 최대 깊이 설정( 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회 이기 때문에 추가 필요)
input = sys.stdin.readline

n = int(input().rstrip())
pic = [list(input().rstrip()) for _ in range(n)]
visited=[[False]*n for _ in range(n)]

dxdy = [[-1,0],[1,0],[0,-1],[0,1]]
rg_y_cnt, rg_n_cnt = 0, 0

# 색상이 같은 경우 dfs하여 그룹 방문처리
def dfs(x,y):
    # 현재 색상 좌표를 방문
    visited[x][y]= True # 방문처리
    current_color = pic[x][y]

    for dir in dxdy: # 상하좌우 방문
        nx,ny = x+dir[0],y+dir[1]
        if 0<= nx <n and 0<= ny <n:  # 범위 내에 있고
            if visited[nx][ny]==False: # 미방문인 경우
                if pic[nx][ny] == current_color: # 현재 좌표의 색상과 상하좌우 좌표 색상이 같으면 끝까지 탐색
                    dfs(nx,ny)

# 미방문인경우 dfs하여 그룹 탐색
for i in range(n):
    for j in range(n):
        if visited[i][j]==False:
            dfs(i,j)
            rg_y_cnt+=1

# 적록색맹의 경우 R,G 구분 못 하므로 G로 통일
for i in range(n):
    for j in range(n):
        if pic[i][j]=='R':
            pic[i][j]='G'

# 방문처리 초기화
visited = [[False]*n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if visited[i][j]==False:
            dfs(i,j)
            rg_n_cnt+=1

print(rg_y_cnt,rg_n_cnt)

'Etc > PS' 카테고리의 다른 글

BOJ_2441 별 찍기 - 4 - Python3  (0) 2022.07.20
BOJ_10870 피보나치 수 5 - Python3  (0) 2022.07.20
BOJ_2178 미로 탐색 - Python3  (0) 2022.07.14
BOJ_11279 최대 힙 - Python3  (1) 2022.07.11
BOJ_1927 최소 힙 - Python3  (0) 2022.07.11

그래프

여러 개체들이 연결되어 있는 자료구조

탐색

특정 개체를 찾기 위한 알고리즘

대표적 문제 유형

  1. 경로탐색 유형 (최단거리, 시간)
  2. 네트워크 유형 (연결)
  3. 조합 유형 (모든 조합 만들기)

 

DFS(Depth-Firsh Search) 깊이 우선 탐색

  • 한 놈만 끝까지 패는 유형

구현 방법

  • 재귀함수가 가장 일반적
  • 한 가지 방법을 끝까지 다 해보고 다음 방식 동작

 

BFS(Breadth-First Search) 너비 우선 탐색

  • 여러 놈을 한대씩 때리면서 가는 유형

구현 방법

  • Queue / LinkedList 사용이 가장 보편적

 

DFS/BFS 알고리즘 판단 방법

  • 자신있는 알고리즘으로 탐색
  • DFS의 장점: 하나의 조합을 완성해서 정답과 비교하는 방식임으로 동작 검증이 쉽다
  • BFS의 장점: 시간복잡도가 낮다(효율성 TC에 유리)

 

참조

'CS > DSA' 카테고리의 다른 글

[자료구조] Array (배열) & LinkedList (연결리스트)  (0) 2022.08.01

+ Recent posts