Flood fill 알고리즘 (카카오프렌즈 컬러링북 문제 풀이)

Flood fill 알고리즘 (카카오프렌즈 컬러링북 문제)

문제내용 : 위와같이 배열로 된영역에 특정 색이 값으로 주어지면 영역의 개수와, 가장 큰 영역이 차지하고 있는 칸 개수를 출력하는 문제입니다.

입력형식 : 배열의 크기를 나타내는 m과 n을 입력받아서 2차원 배열 picture를 참고해서 문제를 풀면된다.

출력형식 : 출력은 answer 배열로 2개의 정수를 가지는 2칸짜리 배열이다. 영역의 개수와 가장 큰영역이 차지하고있는 칸 개수를 순서대로 answer배열에 담아 반환하면된다.

풀이 : 우선 vector를 사용하기 때문에 include 해준다. 그리고 전역변수로 vector를 하나 선언한다. 이때 이차원 배열처럼 사용할 것이므로 벡터선언시 코드 6라인과 같이 선언한다.

 flood_fill 함수 : flood_fill함수는 type, x, y, m, n을 입력받는다. 이때 코드 11번 라인에서는 배열의 범위를 벗어나는지 검사한다. 왜냐 flood fill함수는 상하좌우를 재귀적으로 검사하는 함수이기 때문에 상하좌우 검사시 배열의 범위를 벗어난 곳에 검사하게되면 오류가 발생하기 때문에 검사한다.

 이때 if문의 가장 마지막 조건으로 type을 검사해서 주어진 type과 같은지 최종으로 검사한다. 즉 빨간색을 1이라고 했을 때 1만 검사해주기 위해서 이다. 이때 if문의 특성 ||사용시 순차적으로 검사하는 특징을 이해하고 가장 마지막 부분에 조건을 주어야 제대로된 결과를 얻을 수 있다.

 조건을 통과했다면 해당 영역은 통과했기 때문에 sum에 1을 대입하고 다시 검사하지 않기위해 빈영역으로 처리하도록 0을 area에 대입한다. (14~15라인)

 그후 17~20라인에서 재귀적으로 상하좌우를 검사하도록 해준다. 한 영역의 체크가 끝났다면 22라인 에서 결과를 반환하고 최종 종료된다.

(※ 9라인 sum, 12라인 return 0 등 에대한 코드수정(효율성)은 패스..)

solution함수 : 해당 함수는 출력결과인 answer배열을 반환하는 기능을 수행한다.

 주어진 m, n 크기와 picture배열을 가지고 모두 순회하며 flood fill함수를 실행한다. 이때 33라인에서 0인경우 (원래 비어있거나, 검사를 한 경우) flood fill을 수행하지 않고 continue해버리며, 아닐 경우 영역크기를 계산하게된다.

 이때 가장 큰 영역이 차지하는 개수(38라인), 영역의 개수(39라인)을 갱신하며 마지막으로 결과를 2차원 배열로 반환한다.

 main 함수 부분 : 찾아보니 카카오 코드 페스티벌에서는 main함수를 제외하고 제출을 한다고한다. 그래서 임의로 main함수를 작성하여 결과를 확인했다.

 50~61라인은 입력을 받는 부분이다. 주의할 점은 배열의 내용입력시 하나하나 쳐준뒤 엔터를 눌러주어야한다. 한자리 수로 입력받도록 처리하지 않아서 연달아 입력 불가능하기 때문이다.

 결과가 제대로 뜨는 것을 확인할 수 있고 67라인은 main함수가 종료되면 결과를 볼 수 없기 때문에 입력을 걸어둔 것이다.

결론

 처음에 문제를 봤을 때 재귀로 푸는 것과 어떻게 풀지에 대해서는 구상이 떠올랐는데 전역변수로 해도 된다는 것을 미쳐 생각하지 못해서 헤매다가 결국 몇몇 flood fil 알고리즘을 본뒤 복기하면서 코드를 작성하여 풀었다.

 간단하지만 재귀에 대해서 이해하고 있어야 풀 수있는 문제였고 flood fill에 대해서 알 수 있었던 기회가 되서 좋았다.

code.txt

다른 글 : 2018/06/04 - [algorithm] - ECDSA(타원 곡선 전자 서명 알고리즘) for 파이썬(python) library