1043: 위성 사진

Link : judge.koreatech.ac.kr/problem.php?id=1043

---

1. 문제

• 농부 존은 W x H  (1 <= W <= 80, 1 <= H <= 100) 크기의 자신의 농장 위성사진을 구했습니다. 존은 자신의 농장중 목초 영역의 최대 너비가 얼마인지 측정하고 싶어 합니다.
  위성사진을 간단히 별(*) 과 점(.) 으로 표현을 하면, 별이 목초를 의미하고 점은 목초가 아닌곳을 의미합니다. 여기서 이어져 있다는건 가로/세로로 붙어있다는걸 뜻하고 대각선으로 붙어있는건 이어져 있는게 아닙니다.
  만약 10x5 의 농장의 위성사진이 아래와 같이 있다고 해봅시다.
  

  
  ..*.....**
  .**..*****
  .*...*....
  ..****.***
  ..****.***
  
  이 사진 에는 총 3개의 이어져있는 목초가 있는데, 각각의 크기는 4, 16, 6 이 됩니다.  농부 존을 도와서 위성사진에 있는 목초중에서 가장 큰 영역이 몇인지 구해주세요.

 

---

2. 문제의 조건

• 1 <= W <= 80
• 1 <= H <= 100

 

---

3. 문제 접근

• 시간 복잡도
  
  해당 문제는 유형이 주어져있기 때문에 시간복잡도를 따로 측정하지 않았습니다.

 

• 아이디어
  
  이런 문제는 BFS문제입니다. 너비를 구하는 방식으로 접근하시면 됩니다.

 

---

4. 풀이 방법

• 맵에 *인 부분이 있으면 BFS탐색을 진행합니다.
• que에 start를 지정해두고 que의 크기가 0이 될 때까지 반복합니다.
• 우선 현재 위치를 .으로 바꾸어줍니다.
• * -> .으로 바꾸었으면 크기가 1 증가하므로 counter를 증가시킵니다.
• 대각선으론 움직이지 못하고 왼쪽, 오른쪽, 위, 아래 갈 수 있다면 que에 등록합니다.
  (기본적으로 BFS는 FIFO로 처리하는 것이 좋습니다. 또한 deque를 이용하여 popleft append pop 등 O(1)에 처리할 수 있는 자료구조를 사용하는 것이 좋습니다만, 저는 편의를 위하여 set으로 진행하였습니다.)
• 이 때,
  ***
  ***
  같은 경우를 걸러내기 위해서 중복을 제거해줘야합니다.
  (0, 0)일 경우 오른쪽(0, 1), 아래(1, 0)으로 2개가 나오는데
  (1, 1)일 경우 .으로 안지워졌다면 왼쪽(1,0), 위(0, 1)가 중첩 상태가 되어서 중복을 제거해야 합니다.

 

---

5. 소스코드

• cjw-git.tistory.com/135

 

---

 

cjw.git@gmail.com