[BJ] 1926 - 그림 (BFS)

 

문제를 쪼개서 생각해보자 항상 문제를 쪼개서 생각하는 습관을 들이자.

자 열과 행이 최대 1 < 500개인 2차원배열이 필요하고 열과 행을 입력하여 그 열과 행만큼 입력을 받아야한다.

그리고 그림의 개수, 최대 그림 넓이를 출력하는 문제이다.

1. 열과 행 입력 및 열과 행에 크기에 맞는 입력이 필요함.  =  2중for문

그리고 시작점이 없으니 1이 적힌 인덱스를 찾아야한다 또 열과 행을 돌아야함.

2. 2중for문으로 1이 적인곳을 찾아냄 대신 0이거나 이미 방문했다면 건너뛰면됨

찾아냈다면 그쪽은 1이 있는곳이므로 즉 그림의 개수의 count를 늘리면됨

3. 1을 찾았다면 방문했다고 해주고 q에 삽입함.

4. q의 front를 다른 변수에 넣어주고 q의값을 뻄 그리고 q의 x값 y값을 동서남북으로 비교하며 동서남북에 1이 있다면 방문했다고 넣어주고 q의 삽입함 이 과정에서 인접한곳이 없어서 끝나게된다면 그것이 곧 그림의 넓이가 됨.

 

문제를 쪼개서 생각하고 항상 적어넣고 문제를 풀어보자 이해가 안된다면 그림으로라도 그려서 생각하자 단계별로