[BOJ 1012] 유기농 배추 (C++)

Problem

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

1012번: 유기농 배추

Comment

유기농 배추가 잘 담길 수 있도록 cin으로 좌표값을 받아서 cabbage 배열에 1로 저장해줍니다. 잘 저장된 cabbage 배열을 반복문으로 쭉 돌립니다. 0이 나오면 유기농 배추가 없는 것이니 그냥 넘어가고 1이 나오면 BFS를 해줍니다(사실 여기서 BFS를 하든 DFS를 하든 상관없습니다. 근데 전 BFS로 구현했습니다.)

 

BFS 함수로 넘어가서, 1이 나온 그 자리를 기준으로 상하좌우를 살펴봐야 합니다. 방향 표시를 용이하게 해주는 dx와 dy 배열을 이용해서 찾아줍니다. (이 때, 유기농 배추를 담고 있는 농장을 벗어나지 않게 조심해야 합니다.) 만약 유기농 배추를 찾게 된다면 두 가지 작업을 해주어야 합니다.

1. 원래 유기농 배추가 있던 자리를 0으로 만들어줍니다. 왜냐하면, main 함수에서 유기농 배추 농장 안에 있는 모든 인덱스 값을 돌고 있기 때문에 중복으로 카운트 될 수 있기 때문입니다.

2. 상하좌우 해서 찾아낸 유기농 배추를 큐에 추가합니다.

 

그렇게 찾으면 서로 연결되어 있는 유기농 배추들을 알 수 있고, 배추흰지렁의의 최소 마리 수를 알 수 있습니다.

Code

Result

Remark

배열을 다룰 때 가로와 세로 작성법에 혼동이 가지 않도록 주의해야 합니다.