[백준] 4963. 섬의 개수 (실버2, Python)

풀이

처음에 입력값의 의미를 이해하지 못했다....

다른 블로그랑 GPT한테 물어보고 이해했다.... ㅎ

테스트 케이스 개수가 주어지는 것이 아니라 w,h와 지도정보를 계속 제공하다가 0 0를 만나면 프로그램 종료인 것이었다..!

 

 

Queue를 활용하여 BFS로 풀었다. 현재 노드와 근접한 노드먼저 확인하는 것이 좋다고 판단했기 때문이었다.

 

메인

0 0을 만나면 프로그램 종료이기 때문에 while문으로 반복하다가 0 0일 경우 빠져나가도록 구현했다.

 

주어진 땅, 바다 정보 저장 후, 배열을 돌면서 미방문이면서 땅인 노드에서 findLand(x, y) 함수를 호출했다.

 

 

findLand(x, y) 함수

해당 함수에서는 매개변수로 주어진 x,y 노드를 기준으로 8방향의 노드를 확인한다. 위에서 언급했다 싶이 BFS로 판단하여 큐를 사용했다.

 

큐에 주어진 x, y를 저장한다. 여기서 큐는 땅이면서 방금 방문한 노드를 저장한다. 해당 노드들을 하나씩 꺼내어 각 방향의 노드의 정보를 꼭 확인하여야만 한다.

 

보통 문제에서 앞뒤위아래의 4가지 방향만 확인하는데 이번에는 대각선까지 확인하기 때문에 총 8개의 방향이다.

아래 배열에 움직일 방향에 대해서 저장한다.

 

 

큐에 저장된 모든 노드를 확인하기 위해 큐에 원소가 존재할 때까지 반복 수행한다. 방향값을 저장한 위의 배열을 기준으로 움직일 노드의 x, y값을 구한다.

 

이제 해당 노드가 각 방향에 있는 노드가 아직 미방문이면서 Land인지 확인한다. 조건에 충족하면 방문 체크와 큐에 해당 노드를 저장했다.

 

while문이 종료되면 연결되어 있는 땅을 모두 방문했다는 의미이기 때문에 while문 종류 후, result 변수에 +1한다.

최종 코드

import queue

def findLand(x, y):
    global result
    nearLand = queue.Queue()
    nearLand.put([x, y])
    
    # 앞뒤위아래 / 대각선위앞 & 대각선위뒤 & 대각선아래앞 & 대각선아래뒤
    moveXArr = [0, 0, -1, 1, -1, -1, 1, 1]
    moveYArr = [1, -1, 0, 0, 1, -1, 1, -1]
    
    while nearLand.qsize() > 0:
        node = nearLand.get()
        for i in range(len(moveXArr)):
            moveX = node[0] + moveXArr[i]
            moveY = node[1] + moveYArr[i]
            
            if moveX >= h or moveY >= w or moveX < 0 or moveY < 0:
                continue
            
            if mapInfo[moveX][moveY] == 1 and not mapCheck[moveX][moveY]:
                nearLand.put([moveX, moveY])
                mapCheck[moveX][moveY] = True

    result +=1
            
while True:
    w, h = map(int, input().split())
    
    if w == 0 and h == 0: break
    
    result = 0
    mapInfo = [[0]*w for _ in range(h)]
    mapCheck = [[False]*w for _ in range(h)]
    for i in range(h):
        intList = list(map(int, input().split()))
        for j in range(w):
            mapInfo[i][j] = intList[j]
    
    for x in range(h):
        for y in range(w):
            if mapInfo[x][y] == 1 and not mapCheck[x][y]: findLand(x, y)

    print(result)

 

 

백준 문제

https://www.acmicpc.net/problem/4963

 

GitHub

https://github.com/ujin302/CodingTest_2023/blob/main/Code/BackJun/silver/s2/s2_4963.py