[C++] 백준 1012번:유기농 배추

문제 링크

1012번: 유기농 배추

 

문제 설명

한나는 자신의 땅에 배추를 군데군데 심어놓은 상태다. 아래는 현재 한나의 땅 상태고, 1은 배추가 심어져 있는, 0은 배추가 심어져 있지 않은 땅을 나타낸다. 배추를 해충으로부터 보호하기 위해 배추흰지렁이를 놓을 계획이고 배추흰지렁이는 인접한 땅을 옮겨가며 배추를 보호할 수 있다. 최소의 배추흰지렁이 마리 수를 구하자.

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

위는 땅의 한 예시이고 이 예시에서는 배추흰지렁이는 대각선으로 이동할 수 없기 때문에 최소 5마리가 필요하다.  

왼쪽 상단부터 0행 0열, 오른쪽 하단까지 5행 9열이라고 하자.

1. 0행 0,1열 ~ 1행 1열

2. 3행 4열 ~ 4행 4열

3. 4행 2열 ~ 3열

4. 5행 4열

5. 4행 7열 ~ 5행 9열

 

풀이 방법

땅을 2차원 배열이라고 생각하고 배추가 심어져 있는 땅에 대해 bfs를 진행하고 횟수를 세어주면 된다. 이 때 주의할 점은 배추흰지렁이가 이동할 수 있는 방향은 상, 하, 좌, 우 총 4가지라는 것이다. 이 것을 int dx[4], int dy[4] 배열로 미리 상, 하, 좌, 우로 이동할 수 있는 좌표 방향을 정해주면 풀이가 더욱 간단해진다.

배추흰지렁이가 이동하지 못하는 위치를 체크해줘야 하는 것도 주의하자.

한 번의 bfs를 실행할 때 현재 위치가 범위에 들어가는지, 배추가 심어져 있는지, 방문하였는지를 차례대로 확인하여 bfs를 진행하면 된다.

 

코드

 

메모

22년 첫 블로그 글, 첫 백준 문제 풀이다. 올해도 꾸준하게 작성해서 골드 문제들도 풀어보고 싶다.