[프로그래머스] - 카카오프렌즈 컬러링북

문제

 

입출력 형식

 

입출력 예제

 

솔루션

1. 좌표를 저장하기 위한 Point 클래스를 정의하였다.
2. 답을 제출하기 위한 answer 배열 (각 인덱스 -> 0 : 영역의 총 갯수, 1 : 최대 영역의 넓이), 해당 지점을 방문했는지 여부를 체크하는 visited 배열 (picture와 동일한 크기로) 을 만들어줬다.
3. visitied 배열을 모두 false로 초기화 해준다.
4. picture의 모든 지점을 방문하기 위해 2중 for 루프 (x좌표, y좌표) 를 수행한다.
   1. picture[x][y] 지점을 방문한 적이 있거나 (visited[x][y] == true), 해당 지점이 영역이 아니라면 (picture[x][y] == 0), 다른 지점을 확인한다.
   2. 조건이 충족하지 않는다면, 영역이므로 넓이 우선 탐색 (BFS) 를 수행한다. 결과부터 얘기하자면, BFS를 수행하고 난 뒤의 영역의 넓이가 현재 최대 영역의 넓이 (answer[1]) 보다 크다면 이를 갱신한다.
      1. BFS 함수에서, 파라미터로 방문 여부 배열 (visited), 그림 상태 (picture), 현재 지점의 좌표 (start) 를 전달 받는다.
      2. 시작 지점의 방문 여부를 true, 영역 넓이 (area) 를 1, 그리고 큐에 현재 좌표를 삽입한다 (Offer()).
      3. 큐가 비어 있지 않은 동안 while 루프문을 수행한다.
         1. 현재 좌표의 동서남북 지점에 대한 좌표를 nx, ny에 넣어주고, 조건에 부합하는지 확인한다.
         2. nx, ny가 그림내 좌표라면 (그림 바깥으로 나가지 않는다면) / 그리고 동서남북 지점이 아직 미방문이며 (visited[nx][ny] == false) / 영역으로 포함이 되지않고 (값이 0) / 현재 지점 (Point cur) 과 그 다음 지점 (nx, ny) 이 동일한 영역이라면 (같은 숫자), nx, ny 지점을 방문표시 해주고 (true로 갱신), 큐에 집어넣은 다음, 영역의 넓이를 1 증가시킨다.
      4. while 루프문을 빠져나오면 area 변수는 해당 영역의 넓이가 될 것이므로, 이 영역의 넓이를 반환한다.
   3. 그리고 영역의 갯수를 1 증가시킨다.

 

Code

• 전체 코드 : https://github.com/SubAkBa/Algorithm_Chung_Son/blob/master/Programmers/Solution_kakaofriendscoloringbook.java

좌표를 저장할 Point 클래스

영역의 크기를 찾을 넓이 우선 탐색인 BFS 함수

메인 Solution 함수

 

결과