[백준 4963] 섬의개수 - Python

이번 백준 4963번은 대각선도 고려해줘야 한다는 점에서 많이 어려웠다...

bfs 공부한지 이제 주말빼고 3일정도 지났는데 이제야 슬슬 감이 오기 시작 ㅎㅎ

이전에 풀었던 문제들도 곧 올릴 예정 !! 😊

 

from collections import deque
def bfs(x,y):
    queue = deque()
    queue.append((x,y))

    #대각선 확인
    direction = [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]
    while queue:
        current_x, current_y= queue.popleft()
        for i in range(8):
            dx = current_x + direction[i][0]
            dy = current_y + direction[i][1]

            #전체 지도 안에 존재하면서 , 땅인경우 !
            #이때 dx가 h보다 작고, dy가 w보다 작아야하는 이유는
            #dx값이 커지면 [변하는값][고정] 이기때문에 x좌표가 변하면 h값으로 비교해주어야한다.
            #dy값이 커지면 [고정값][변하는값] 이기때문에 y좌표가 변하면 w값으로 비교해주어야한다.
            if 0<=dx<h and 0<=dy<w:
                if newMap[dx][dy] == 1:
                    newMap[dx][dy]=0
                    queue.append([dx,dy])

answer = []
while True:
    w,h = map(int,input().split())

    # 입력값이 0 0 이면 끝내기
    if w== 0 and h ==0:
        break

    #입력시 섬의 개수를 담아둘 배열을 0으로 초기화
    answer.append(0)

    #입력을 바탕으로한 땅과 바다로 이루어진 지도 (0은 바다, 1은 땅)
    newMap = []

    # 땅 1 , 바다 0
    for i in range(h): #h개수만큼 높이
        newMap.append(list(map(int,input().split()))) #w 개수만큼 입력

    cnt = 0
    #세로
    for i in range(h):
        #가로
        for j in range(w):
            #땅인지 확인
            if newMap[i][j] ==1:
                cnt += 1
                bfs(i,j)
                #땅이었기 때문에 섬의 수를 cnt로 카운트해주고, 위에 answer의 해당 index값에 0으로 초기화 해준 자리에 cnt넣기
                answer[len(answer)-1]=cnt

for i in range(len(answer)):
    print(answer[i])