모양 만들기
-
백준 16932번 모양 만들기PS 2020. 3. 7. 00:55
https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다. 배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자. www.acmicpc.net 0을 하나하나 선택해서 1로 바꾸로 bfs를 돌린다면 매우 비효율적일 것 입니다. 처음에는 bfs를 돌리면서 1로 바꾸는 능력 사용여부를 확인해준다면 될 것이라고 생각했습니다. 실패했습니다. 그래서 모든 0에 대해 1로..