#백준, [#1926_그림], #BFS, #DFS
문제: https://www.acmicpc.net/problem/1926
문제
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.
입력
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)
출력
첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.
예제 입력 1 복사
6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1
예제 출력 1 복사
4
9
이런 그리드 문제는 보자마자 접근을 BFS와 DFS방식으로 해야한다는 느낌이 딱 올 것이다. 아닌 경우도 있겠지만...
나는 BFS로 문제를 풀었다. 흔히 BFS가 가장 좋은 방법일 경우가 많다. 왜냐하면 BFS는 DFS보다 훨씬 빠르고 효율적인 속도로 Searching을 하기 때문이다. 방면에 DFS가 효율적이고 확실하게 해결할 수 있는 문제도 있으니 DFS의 개념과 응용할 수 있는 능력을 길러 두는 것도 중요하다. 하지만 이 문제는 BFS가 가장 제일 어울리다고 생각했기에 BFS로 풀었다.
가로나 세로로 연결된 경우만 이어져있는 그림이라고 설명을 하였기에 dx, dy를 상하좌우만 고려하도록 setting해 두었다.
그리고 visited라는 방문했다는 것을 기록해 두는 리스트를 선언해두었고, def bfs() 함수를 만들어서 잘 bfs를 구현하였다.
흔히 우리는 알고 있다. DFS는 스택과 재귀로 구현할 수 있고, BFS는 큐로 구현을 한다는 것을 말이다. 어려운 것이 아니니 기억해두자.
DFS로 문제를 풀어보는 것은 나는 따로하지 않았지만 풀어보는 것을 추천하며 풀어본 분들은 댓글로 저에게 공유해주시면 감사해용~