[Python] 백준 #4963- 섬의 개수

문제

---

 

4963번: 섬의 개수

코드

---

My answer

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

direct=[[1,0],[-1,0],[0,1],[0,-1],[1,-1],[1,1],[-1,-1],[-1,1]]

def bfs(x,y):
        Q=deque()
        Q.append((x,y))
        visit[x][y]=1
        
        while Q:
            x,y=Q.popleft()
            for i in range(8):
                n_x,n_y=x+direct[i][0],y+direct[i][1]
                if(0<=n_x<h and 0<=n_y<w):
                    if(visit[n_x][n_y]==0 and graph[n_x][n_y]==1):
                        visit[n_x][n_y]=1
                        Q.append((n_x,n_y))  
        return 0

while(1):
    w,h=map(int,input().split())
    if(w==0 and h==0):
        break
    graph=[list(map(int,input().split())) for _ in range(h)]
    visit=[[0]*w for _ in range(h)]
    cnt=0
    for i in range(h):
        for j in range(w):
            if(graph[i][j]==1 and visit[i][j]==0):
                    bfs(i,j)
                    cnt+=1
    print(cnt)

 

Another answer

import sys
sys.setrecursionlimit(10**6)

dr = [-1, -1, -1, 0, 0, 1, 1, 1]
dc = [-1, 0, 1, -1, 1, -1, 0, 1]

def dfs(a, b):
    global island, visited
    visited[a][b] = 1
    for dir in range(8):
        nr = dr[dir] + a
        nc = dc[dir] + b
        if nr >= 0 and nr < h and nc >= 0 and nc < w:
            if arr[nr][nc] == 1 and visited[nr][nc] == 0:
                dfs(nr,nc)

while True:
    island = 0
    w, h = map(int,input().split())
    if w == 0 and h == 0 :
        break
    arr = []
    visited = [[0] * w for _ in range(h)]
    for i in range(h):
        arr.append(list(map(int,input().split())))
    for i in range(h):
        for j in range(w):
            if arr[i][j] == 1 and visited[i][j] == 0:
                dfs(i,j)
                island += 1
    print(island)

풀이

---

이 문제도 전형적인 dfs, bfs문제로 그냥 1인 되어있는 블럭들을 방문하는 문젠데 다른 문제와 다른게 대각선도 가능하다는 것이다. 따라서 대각선만 고려해주면 쉽다. 그리고 w랑 h 헷갈리지말기