[인프런 | 파이썬 알고리즘] 섬나라 아일랜드(DFS, BFS, 8방향 좌표 이동)

너무 좋은 코테공부용 강의 ㅠㅠ

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

 

문제

섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대 각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

입력설명

첫 번째 줄에 자연수 N(1<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.

출력설명

첫 번째 줄에 섬의 개수를 출력한다.

입력예제

7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0

출력예제

5

 

 

문제풀이

단지 번호붙이기와 비슷한 문제

상하좌우뿐만 아니라 대각선까지 8방향을 이동하면서 순회한다.

 

BFS 버전

from collections import deque

def BFS(start_x, start_y, map_data, count, n) :
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]        #top 0, top-right 1, right 2, right-bottom 3, bottom 4, botton-left 5, left 6, left-top 7
    dy = [0, 1, 1, 1, 0, -1, -1, -1]

    dq = deque()                                                #BFS를 위한 큐 생성
    count += 1
    
    dq.append((start_x, start_y))           #1. 큐에 시작점 추가
    map_data[start_x][start_y] = 0          #2. 큐에 넣은 시작점은 방문처리
    
    while dq :
        now_idx = dq.popleft()              #현재 방문 노드
        
        for i in range(8) :                 #8방향 이동(top 0, top-right 1, right 2, right-bottom 3, bottom 4, botton-left 5, left 6, left-top 7)
            next_x = now_idx[0] + dx[i]     #큐에 들어간 좌표 중 연결된 다음 x좌표[0]
            next_y = now_idx[1] + dy[i]     #큐에 들어간 좌표 중 연결된 다음 y좌표[1]
            
            #x좌표 내 and y좌표 내에서 이동 and 인접한 다음 방문할 곳이 길(1)인 경우 이동
            if 0 <= next_x <= (n-1) and 0 <= next_y <= (n-1) and map_data[next_x][next_y] == 1:   
                count += 1
                map_data[next_x][next_y] = 0    #방문한 곳은 벽(0)처리
                dq.append((next_x, next_y))
    return count

def solution() :
    n = int(input())
    maps = []
    result = []

    for i in range(n) :         #map 입력 받기
        temp = list(map(int, input().split()))
        maps.append(temp)

    #완전 탐색 하면서 1 있는 곳은 BFS 시작
    for i in range(n) :
        for j in range(n) :
            if maps[i][j] == 1 :
                count = 0
                count = BFS(i, j, maps, count, n)
                result.append(count)

    print(len(result))


solution()

# 7
# 1 1 0 0 0 1 0
# 0 1 1 0 1 1 0
# 0 1 0 0 0 0 0
# 0 0 0 1 0 1 1
# 1 1 0 1 1 0 0
# 1 0 0 0 1 0 0
# 1 0 1 0 1 0 0

 

DFS버전

def DFS(current_x, current_y, map_data) :
    global count
    global n

    dx = [-1, -1, 0, 1, 1, 1, 0, -1]        #top 0, top-right 1, right 2, right-bottom 3, bottom 4, botton-left 5, left 6, left-top 7
    dy = [0, 1, 1, 1, 0, -1, -1, -1]

    count += 1
    
    map_data[current_x][current_y] = 0
    
        
    for i in range(8) :                 #8방향 이동(top 0, top-right 1, right 2, right-bottom 3, bottom 4, botton-left 5, left 6, left-top 7)
        next_x = current_x + dx[i]     #연결된 다음 x좌표[0]
        next_y = current_y + dy[i]     #연결된 다음 y좌표[1]
        
        #x좌표 내 and y좌표 내에서 이동 and 인접한 다음 방문할 곳이 길(1)인 경우 이동
        if 0 <= next_x <= (n-1) and 0 <= next_y <= (n-1) and map_data[next_x][next_y] == 1:   
            DFS(next_x, next_y, map_data)

def solution() :
    global n
    global count

    n = int(input())
    maps = []
    result = []

    for i in range(n) :         #map 입력 받기
        temp = list(map(int, input().split()))
        maps.append(temp)

    #완전 탐색 하면서 1 있는 곳은 BFS 시작
    for i in range(n) :
        for j in range(n) :
            if maps[i][j] == 1 :
                count = 0
                DFS(i, j, maps)
                result.append(count)

    print(len(result))


solution()

# 7
# 1 1 0 0 0 1 0
# 0 1 1 0 1 1 0
# 0 1 0 0 0 0 0
# 0 0 0 1 0 1 1
# 1 1 0 1 1 0 0
# 1 0 0 0 1 0 0
# 1 0 1 0 1 0 0