백준 4963번(섬의 개수) 파이썬

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

4963번: 섬의 개수

이번 문제는 기본적인 bfs 문제로 풀 수 있다. 하지만 다른 문제와 차이점은 입력예제에 조건이 있다는 것이다.

보통 몇번 반복할지 입력을 받고 입력을 실시하는데 이 문제는 몇번 반복할지 묻지 않고 0,0 이라는 숫자가 나올때까지 프로그램을 계속 실행해야 하는것이다. 처음에 문제를 보고 음.. 살짝 까다롭겠는데 생각을 했지만 bfs에 나오는 큐를 사용한 반복을 적용해서 입력예제를 똑같이 구현했다. 그렇게 푸니까 바로 풀렸다.

알고리즘 적으로 어려운 문제는 아니였다.

 

import sys
from collections import deque

input = sys.stdin.readline

def bfs(a,b):
    q=deque()
    q.append((a,b))
    graph[a][b]=0 # 방문처리
    
    while q:
        x,y = q.popleft()
        
        for i in range(8): # 8개의 방향을 탐색
            nx = x + dx[i]
            ny = y + dy[i]
            
            if (0<=nx<h and 0<=ny<w and graph[nx][ny] == 1): # 벽에 안닿고 가야할 방향에 미방문일때
                q.append((nx,ny)) # 가야할 방향을 큐에 추가
                graph[nx][ny]=0 # 방문처리

dx = [1,-1,0,0,1,1,-1,-1] #상하좌우 대각선까지 
dy = [0,0,1,-1,1,-1,1,-1] # 총 8개의 방향을 선언

q1 = deque() # 입력 예제와 같게하기 위해 큐를 하나 생성
q1.append(map(int,input().split())) # 첫번째 입력

while q1: # 입력 예제가 빌때까지 반복
    cnt=0
    graph = []
    w,h = q1.popleft()
    if w == 0 and h == 0: # 0,0이 입력되면 종료
        break
    for _ in range(h):
        graph.append(list(map(int,input().split()))) # 그래프 입력
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1: # 그래프탐색
                bfs(i,j)
                cnt+=1
    print(cnt) # 정답 출력
    q1.append(map(int,input().split())) #다음 입력을 이어서해준다

코드를 보면 bfs 안에 있는 while문과 밖에 있는 while문의 흐름이 비슷한걸 볼 수 있다.

이렇게 문제안에서 힌트를 찾아서 풀 수 있었다.