[백준] 4963번 섬의 개수(python)

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

4963번: 섬의 개수

 

1. 난이도 실버2 (🥈)

 

2. 내가 작성한 코드

from collections import deque
import sys

input = sys.stdin.readline

def bfs(k):

  queue.append(k)

  visit[k[0]][k[1]] = 1

  dx = [1, 1, 0, -1, -1, -1, 0, 1]
  dy = [0, 1, 1, 1, 0, -1, -1, -1]
  
  while queue:
    x,y = queue.popleft()

    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx<0 or ny<0 or nx>=h or ny>=w:
        continue
    
      if maps[nx][ny] == 0:
        continue

      if visit[nx][ny] == 0:
        visit[nx][ny] = 1
        queue.append((nx,ny))


while True:

  w,h = map(int, input().rstrip().split()) #w = 열, h = 행

  if w == 0 and h == 0:
    break

  maps = [list(map(int, input().rstrip().split())) for _ in range(h)]
  visit = [[0] * w for _ in range(h)]
  lands = []
  cnt = 0

  queue = deque()

  for i in range(h):
    for j in range(w):
      if maps[i][j] == 1:
        lands.append((i,j))

  for k in lands:
    if visit[k[0]][k[1]] == 0:
      bfs(k)
      cnt += 1

  print(cnt)

 

그동안 풀어왔던 문제와 많이 유사했다.

 

상,하,좌,우,대각선을 모두 다녀와야 하기 때문에

 

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

 

로 설정한다.

 

이후에는 방문한 적 없는 섬을 방문하며 bfs 를 실행시키면 됨!

 

나처럼 lands 라는 list 를 굳이 쓸 필요는 없는 것 같다.

 

이중 for문을 이용할 때 maps[i][j] == 1 or visit[i][j] == 0 인 곳을 방문하면 되는듯