[백준 1012번] 유기농 배추 - 자바(JAVA)

 

 

 

www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

문제 접근

배추가 심어진 공간의 갯수를 구해야 하기에 넓이 우선 탐색 기법인 BFS를 이용하기로 하였습니다. 두 가지 풀이법을 생각했는데요.

 

1. 좌표 입력과 동시에 하나의 범위에 속하는지 아닌지 체크
   
   
2. 2차원 배열에 배추가 심어진 범위를 표시한 뒤, 필요한 벌레 카운트

하지만 1번 접근법에는 오류가 존재했습니다. 좌표가 입력됨과 동시에 상하좌우로 1이 있는지 없는지 체크한 뒤, 인접한 1이 없다면 갯수를 카운트했습니다. 이 방법에 치명적인 오류는 갯수가 순서대로 일정하게 입력되지 않아, 입력되는 과정에서 A의 배추범위와 B의 배추범위가 합쳐질 수 있다는 것입니다. 이런 사항때문에 1번은 적절한 풀이방법이 아니었습니다.

 

1번 풀이

앞서 이야기한 사유로 해당 풀이는 적절하지 못하였습니다. 예외처리를 한다면 달라질 수 있겠지만요.

 

정답

 

풀이법은 아래와 같습니다.

 

• 2차원 배열을 생성하며 값을 삽입합니다. 주의할 사항은 모든 풀이에서 입력되는 값의 행, 열을 구분해야 합니다.
  
  
• BFS 알고리즘으로 상하좌우 탐색하며, 인접한 BUG는 VISITED값으로 바꾸어주어 방문한 값을 체크합니다.
  
  
• 중요한 사항은 해당 값 체크가 모두 끝난 뒤 필요한 벌레수를 카운트해야 합니다.
  
  
• 여기서 사용되는 자료구조는 Queue입니다.