[백준] 1926번: 그림 (C++ 풀이)

문제

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

 

풀이

이 문제는 단지번호붙이기(https://www.acmicpc.net/problem/2667) 문제와 거의 유사하다고 할 수 있다.

bfs로 풀었고,

가장 넓은 그림의 넓이를 구할 때는 단지번호붙이기와 마찬가지로

ans배열을(인덱스가 그룹번호) 만들어서 sort한 후 맨 마지막 인덱스를 출력하도록 하였다.

ans배열의 크기는 int ans[500 * 500 / 2 + 1]; 이렇게 잡았는데

그림의 최대 개수는

1 0 1 0

0 1 0 1

1 0 1 0

0 1 0 1

이런 식일 때가 제일 많으므로 저렇게 잡았다.

 

계속 '틀렸습니다'가 나와서 당황스러웠는데, 그 이유가

그림이 없을 때를 고려하지 않아서 그랬다.

1 1

0

일 때, 그림 개수 0, 가장 넓은 그림의 넓이 0가 나와야한다.

나는 cnt(그림 개수)를 출력 후 바로 0인지 체크하고

0이면 출력한 후 return하도록 구현하였다.

 

코드

https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1926.cpp

 

결과