[김태원 알고리즘] 섬나라 아일랜드 (대각선 FloodFill - DFS & BFS)

사용 언어: Python3

문제

이 문제는 대각선까지 하나의 flood fill로 생각한다는 점을 잘 생각해보자!

풀이

내 풀이 - DFS 사용

dx, dy = [0,-1,-1,-1,0,1,1,1], [1,1,0,-1,-1,-1,0,1] # ✅ 대각선 포함
def DFS(x, y):
    visited[x][y] = 1
    for w in range(8): # ✅ 대각선 포함
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] == 0 or visited[xx][yy] == 1:
            continue
        DFS(xx, yy)

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

cnt = 0
for i in range(N):
    for j in range(N):
        if board[i][j] == 0 or visited[i][j] == 1:
            continue
        cnt += 1
        DFS(i, j)
print(cnt)

추가

만약 각각의 섬에 포함된 원소의 수를 출력하고 싶다면 아래와 같이 하면 된다.

dx, dy = [0,-1,-1,-1,0,1,1,1], [1,1,0,-1,-1,-1,0,1] # 대각선 포함
def DFS(x, y):
    global cnt # 🌟
    visited[x][y] = 1
    for w in range(8):
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        if board[xx][yy] == 0 or visited[xx][yy] == 1:
            continue
        cnt += 1 # 🌟
        DFS(xx, yy)

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if board[i][j] == 0 or visited[i][j] == 1:
            continue
        cnt = 1 # 🌟
        DFS(i, j)
        print(cnt) # 🌟

내 풀이 - BFS 사용

from collections import deque

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]

cnt = 0
q = deque()

dx, dy = [0,-1,-1,-1,0,1,1,1], [1,1,0,-1,-1,-1,0,1]
for i in range(N):
    for j in range(N):
        if board[i][j] == 0 or visited[i][j] == 1:
            continue # ✅ 조건 체크 잊지 말기 !!
        visited[i][j] = 1 # ✅ 방문 체크 잊지 말기 !!
        q.append((i, j))
        while q:
            cur = q.popleft()
            for w in range(8):
                xx, yy = cur[0]+dx[w], cur[1]+dy[w]
                if xx<0 or xx>=N or yy<0 or yy>=N:
                    continue
                if board[xx][yy] == 0 or visited[xx][yy] == 1:
                    continue
                q.append((xx, yy))
                visited[xx][yy] = 1
        cnt += 1 # cnt 누적

print(cnt)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기