백준_4963_섬의 개수

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

해결 방법

> DFS를 이용한다.

 

고찰

> 문제를 보자마자 입력을 어떻게 받아야 할지 고민하였다. 줄마다 입력 개수가 다르기 떄문이다.

> import sys

> input = sys.stdin.readline을 이용한다.

 

참고 자료

> https://rebas.kr/655

BOJ 4963 · 섬의 개수

해결하지 못한 부분

> 백준에서 런타임에러가 나는데 참고한 자료와 차이점을 발견하지 못하여 통과하지 못하였다.

 

코드

import sys

sys.setrecursionlimit(10000) #재귀함수 한계 설정

input = sys.stdin.readline  #readline

 

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

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

 

while True:

    n, m = map(int, input().split())

 

    if n == 0 and m == 0: #런타임에러 수정 부분

        break

 

    island = [list(map(int,input().split())) for i in range(m)] #input

    check = [[False]*n for i in range(m)]   #연결되어 있는지 확인

 

    def dfs(x, y):  #입력 케이스에 대해 섬의 연결을 확인하는 부분

        check[x][y] = True

        for i in range(8):

            nx, ny = x + dx[i], y + dy[i]

            if nx < 0 or nx >= m or ny < 0 or ny >= n:

                continue

            if island[nx][ny] == 1 and check[nx][ny] is False:

                dfs(nx, ny)

 

    count = 0

    for i in range(m):

        for j in range(n):

            if island[i][j] == 1 and check[i][j] is False:

                dfs(i, j)

                count += 1

 

    print(count)