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

📌 난이도, 유형

난이도 : 실버2
유형 : 그래프 이론, 그래프 탐색, DFS, BFS
시간제한 : 1초
메모리제한 : 128MB

---

📌 문제설명

---

📌 입출력 예

---

📄 코드

DFS풀이

import sys
sys.setrecursionlimit(2500)
input = sys.stdin.readline

# 대각선도 움직임이 가능하다.
dx = [-1,-1,-1,1, 1,1, 0, 0]
dy = [0, 1, -1,-1, 1,0, -1, 1]


def dfs(x,y):
    if x < 0 or y < 0 or x >= h or y >= w or graph[x][y] == 0:
        return False
    
    visited[x][y] = True
    graph[x][y] = 0
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        dfs(nx,ny)
    return True

while True:
    w,h = map(int, input().split())
    island = 0 # 섬 개수 출력
    # w,h가 0이 되면 반복문 종료
    if w == 0 and h == 0:
        break
    graph = []
    
    # 좌표 추가
    for i in range(h):
        graph.append(list(map(int, input().split())))

    # 방문한 곳 표시
    visited = [[False] * (w) for _ in range(h)]
    result = 0
    # 그래프 하나씩 탐색하기
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1 and visited[i][j] == False:
                dfs(i,j)
                result += 1
    print(result)

BFS풀이

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

# 대각선도 움직임이 가능하다.
dx = [-1,-1,-1,1, 1,1, 0, 0]
dy = [0, 1, -1,-1, 1,0, -1, 1]

island = 0 # 섬 개수 출력

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    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 or graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx,ny))
    return 1

while True:
    w,h = map(int, input().split())
    island = 0 # 섬 개수 출력
    # w,h가 0이 되면 반복문 종료
    if w == 0 and h == 0:
        break
    graph = []
    
    # 좌표 추가
    for i 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:
                island += bfs(i,j)
    print(island)

---

📝 해설

• 문제에서 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있다고 했으니, 대각선으로 움직이는 것도 고려해야 한다.

# 대각선도 움직임
dx = [-1,-1,-1,1, 1,1, 0, 0]
dy = [0, 1, -1,-1, 1,0, -1, 1]

가운데가 0,0 이라고 할 때

-1,1	0,1	1,1
-1,0	0,0	1,0
-1,-1	0,-1	1,-1

이런 식으로 움직이므로
dx,dy를 추가해주면 된다.

• 그래프 탐색할 때 조심하기

for i in range(h): # w 아님!
    for j in range(w): # h 아님!
        if graph[i][j] == 1:
            island += bfs(i,j)

무방향 그래프가 아니므로 가로길이(w), 세로길이(h)를 신경써줘야 한다.

if x < 0 or y < 0 or x >= h or y >= w or graph[x][y] == 0:
	return False

함수안에 있는 조건문도 x >= w or y >= h가 아니다.