[2017 카카오코드 예선] 컬러링북 - 파이썬

문제

https://programmers.co.kr/learn/courses/30/lessons/1829

코딩테스트 연습 - 카카오프렌즈 컬러링북

영역의 수와 가장 큰 영역의 넓이를 구하는 문제이다.

 

문제풀이

흔히 볼 수 있는 bfs 문제와 유사하다.

que에 좌표를 넣고 que가 빌 때까지 move를 이용해 주위 좌표(상,하,좌,우)를 탐색하고, 동일한 값을 지닌 좌표는 que에 추가해주는 방식으로 탐색을 진행한다. 해당 좌표를 방문했다면 check 값을 바꿔주어 방문 체크를 해준다.

 

bfs를 새로 실행할 때 마다 새로운 영역을 탐색하는 것이므로 영역 값(answer[0])에 1을 더해주고,

bfs를 return 하기 전에 기존의 가장 큰 영역 값(answer[1])과 비교하여 값을 갱신해준다.

 

 

코드

import sys
from collections import deque

def bfs(x,y,answer):
	que=[(x,y)]
	temp=picture[x][y]
	move=[[1,0],[-1,0],[0,1],[0,-1]]
	count=1
	check[x][y] =1
	while que:
		x,y=que.pop()
		for i in move:
			dx=x+i[0]
			dy=y+i[1]
			if 0<=dx<m and 0<=dy<n:
				if temp==picture[dx][dy] and not check[dx][dy]: ##색이 같으면서 방문하지 않은 경우
					count+=1
					check[dx][dy]=1
					que.append((dx,dy))
					
	answer[0]+=1
	answer[1]=max(answer[1],count)
	return 

def solution(m, n, picture):
	answer = [0,0]
	for i in range(m):
		for j in range(n):
			if check[i][j]==0 and picture[i][j]!=0:
				bfs(i,j,answer) #새로운 영역 탐색
	return answer
    
if __name__ == "__main__":
    input = sys.stdin.readline
    m, n = map(int, input().split())
    picture = [list(map(int, input().split())) for _ in range(m)]
    check = [[0] * n for _ in range(m)]
    number_of_area, max_size_of_one_area = solution(m, n, picture)
    print(number_of_area, max_size_of_one_area)