Diary

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

문제 해석 및 예상 풀이 방법

2차원으로 주어지는 입력 값에서 1로 주어지는 입력을 그림이라 한다.

그림은 상하좌우로만 연결되어 있어야 하며 대각은 이어지지 않는다.

주어진 입력에서 그림의 갯수와 최대크기 그림의 크기를 구한다.

-> BFS로 입력값을 돌며 갯수와 크기를 체크해 주면 해결 가능할 것 같다.

문제 풀이

입력을 받은 후 첫 칸부터 bfs를 돌아주면 되는 간단한 문제였다.

• 입력받은 2차원 배열을 2중 for문을 통해 확인하며 입력값 및 visit 여부를 판단해 bfs를 수행한다.
• bfs를 돌며 그림의 크기를 체크해 주고 반환값으로 크기를 반환한다.
• 반환값들을 vector에 넣어주고, vector를 정렬함으로써 그림의 최대크기를 구하고, vector의 size를 통해 그림의 갯수를 구한다.

코드와 함께 살펴보자

• n : 도화지의 세로 크기
• m : 도화지의 가로 크기
• vector<int> v : 그림의 크기와 갯수를 위한 vector 배열
• map[][] : 도화지의 정보
• visit[][] : 도화지 체크 여부
• moveM[] : 움직일 수 있는 범위(상,하,좌,우)

입력값들을 받고, 매 칸수의 방문 여부와 그림여부를 확인해 bfs함수에 좌표값을 넣어준다.

해당 좌표값에 대한 bfs함수는 그림의 크기를 반환해 준다.

출력에서 테스트케이스 1 1 0 을 입력하였을 경우 0이 나와야 하는데, 이 점을 고려하지 못하여 오류가 발생했었다.

따라서 if 조건문을 이용하여 그림이 하나도 없는 경우 또한 확인해 주었다.

그림이 있는 경우는 그림의 크기를 반환받은 vector<int> v 배열을 sort함수로 정렬하여 주고, 출력 양식에 따라 그림의 갯수 v.size()와 그림의 최대 크기 v[v.size()-1]을 출력하였다.

그림의 좌표를 입력으로 받고, 그림의 크기를 위한 countSell 변수를 0으로 초기 설정한다.

좌표값을 넣어줄 queue에 초기 좌표를 넣고 방문처리까지 완료하고 while문을 수행한다.

q에서 값을 하나 꺼낼때 마다 countSell++를 통해 그림의 크기를 키워주고 상하좌우 이동에 대해 moveM 배열을 이용하여 다음 좌표를 지정한다.

좌표 지정 과정에서 범위와 방문여부, 입력값에 대해 확인해 주고 알맞은 입력값일 경우 q에 넣어주고 방문처리를 한다.

bfs완료 후 그림의 크기인 countSell을 반환한다.

그림의 갯수가 0이 나오는 경우를 체크해주지 못해 런타임 에러가 발생하였다.

해당 경우를 체크해 준 후 40ms로 문제를 해결하였다.

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/BFS/1926.cpp