[CodeUp/2839] 활동 영역 (Python)

Problem : https://codeup.kr/problem.php?id=2839&rid=0

Status : Solved

Time : 00:09:11

 

---

 

문제 설명

 

GS라는 물고기에 대한 연구를 하고 있다. GS는 수온이 일정하게 유지될 때, 안정적으로 활동할 수 있다고 한다.

연구를 위하여 직사각형 형태의 대형 수족관을 만들었다. 수족관의 크기는 세로, 가로가 각각 h, w이다. 각 단위영역의 온도를 조사한 결과 GS가 활동할 수 있는 곳은 1, 그렇지 않은 곳은 0으로 표시한 표를 만들었다.

이 표를 바탕으로 할 때, GS가 활동할 수 있는 총 영역의 수를 구하는 프로그램을 작성하시오.
(“활동할 수 있는 영역”이란 1로 표시된 임의의 영역으로부터 상, 하, 좌, 우로 인접한 1로 표시된 영역들의 집합(덩어리)을 의미한다.)

 

입력 및 출력

 

입력

첫 번째 줄에 수족관의 크기를 나타내는 정수 h와 w가 공백으로 구분되어 입력된다.
다음 줄부터 h줄에 걸쳐서 각 줄에 w개의 0 또는 1로 이루어진 문자열이 입력된다.

[Sub-task Info]
#1 : h, w <= 100 (70%)
#2 : h, w <= 1,000 (30%)

 

출력

 

최대 영역의 개수를 출력한다.

 

입력 예시

 

3 4 1111 1000 1111

 

출력 예시

1

 

 

---

 

풀이

 

이런 류의 문제는 꽤 흔하게 출제되는 바, 공식처럼 외워 두면 만일의 상황 - 취업이라던가 대회라던가 - 에 대비하기 편하다.

 

핵심은 경로 탐색 알고리즘(BFS, DFS)를 이용하는 것.

1. 맵 전체를 탐색하다가,

2. 우리가 찾고자 하는, 방문하지 않은 1을 발견하면

3. 경로 탐색 알고리즘을 이용해 인접한 모든 1의 집합을 탐색하는 것을 반복한다.

4. 그러면 인접한 1들의 집합을 전부 탐색한 셈이므로 이를 카운팅한다.

 

DFS 나 BFS는 비교적 간단하지만... 이것도 따로 정리해서 포스팅하면 괜찮지 싶다. 우선은 여기까지!

 

풀이 코드

import sys
input = sys.stdin.readline

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def dfs(x, y):
  visited[y][x] = True
  q = [(x, y)]
  while q :
    _x, _y = q.pop()
    for i in range(4) :
      ax, ay = _x + dx[i], _y + dy[i]
      if -1 < ax < w and -1 < ay < h and map_list[ay][ax] == '1' and not visited[ay][ax] :
        visited[ay][ax] = True
        q.append((ax, ay))

h, w = map(int, input().split())
map_list = [input().strip() for _ in range(h)]
visited = [[False]*w for _ in range(h)]
result = 0

for i in range(h) :
  for j in range(w) :
    if map_list[i][j] == '1' and not visited[i][j] :
      dfs(j, i)
      result += 1

print(result)

풀이 완료!