[백준] 4963번(python 파이썬) - 섬의 개수

문제 링크: https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	55592	28081	20120	49.253%

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

 

 

 

 

풀이

---

이 문제는 전형적인 bfs문제이다. 

문제에서 하라고 하는 것만 잘 하면된다.

 

풀이방법은 다음과 같다.

 

1. 가로길이, 세로길이를 입력 받는다.

 

2. 그래프를 입력받는다.

 

3. 이중for문을 이용해 전체그래프를 탐색한다. 만약 섬인 부분이 있다면 bfs함수 실행, 결과값 +1

 

4. bfs함수를 만든다. -> graph에 전달된 땅의 좌표에서 연결된 땅들을 전부 바다로 바꾸는 함수

(전달된 땅도 바다로 만든다.)

 

5. 2중for문이 끝난 후 결과값을 결과list에 추가

 

6. 결과 list 출력

 

이 과정을 반복하면 발견된 땅은 모두 바다가 되고 탐색이 끝났을 때는 모든 섬의 개수가 결과리스트에

append된다.

 

bfs함수의 내용은 다음과 같다.

 

모든방향 탐색

dx, dy list에 모든 방향을 적어놓는다.

dx = [1, -1, 0, 0, 1, -1, 1, -1] # 그래프의 탐색 방향
dy = [0, 0, 1, -1, 1, -1, -1, 1]

 while que문 안에서

bfs함수의 인자로 전달된 좌표에다 dx, dy를 더한다.

for i in range(len(dx)):

  nx = x + dx

  ny = y + dy

 

 

이후 nx, ny가 범위안에 있고 nx, ny좌표가 섬이라면 큐에 해당좌표를 넣어주고 그 좌표를 바다로 만든다.

 

이 과정을 반복하면 된다.

 

 이상 오늘 포스팅 끝~~~!

 

 

 

 

 

슬슬 종강할때 된 것 같은데.... (아닌가..?)

 

 

 

 

 

구현 코드

---

from sys import stdin
from collections import deque
input = stdin.readline 

dx = [1, -1, 0, 0, 1, -1, 1, -1] # 그래프의 탐색 방향
dy = [0, 0, 1, -1, 1, -1, -1, 1]

def bfs(x, y):
    que = deque()
    que.append((x, y))
    graph[y][x] = 0
    while que:
       a, b = que.pop()
       for i in range(8):
           ny = b + dy[i]
           nx = a + dx[i]
           if 0<=nx<m and 0<=ny<n and graph[ny][nx] == 1: # 그래프의 탐색조건
               que.append((nx, ny))
               graph[ny][nx] = 0


result = []
while True:
    res = 0
    m, n = map(int, input().split())
    if n == 0 and m == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1: # 해당지점이 땅인 경우만 탐색
                bfs(j, i)
                res += 1 # 땅인경우 결과값 +1
    result.append(res) # 결과 리스트에 추가

for i in result:
    print(i) # 결과 출력