백준 깊이 우선 탐색 4963번

안녕하세요 GDSC ML 멤버 나건주입니다.
파이썬 알고리즘 스터디 7번째 주제 깊이 우선 탐색의 6번째 문제를 풀어보았습니다.
우선 깊이 우선 탐색의 뜻부터 알아보겠습니다.

깊이 우선 탐색

https://www.acmicpc.net/problemset?sort=ac_desc&algo=127

깊이 우선 탐색은
1) 여러 경우의 수 중 하나를 선택
2) 선택 후 가능한 여러 경우의 수 중 또 하나를 선택
하는 식으로 매 단계에서 가능한 것 중 일단 하나를 선택해 끝을 볼 때까지 깊게 들어갑니다.

스택과 큐를 이용하여 많이 탐색합니다.

시간 복잡도
노드 수: V 간선 수: E 시간 복잡도: O(V+E)

4963번 섬의 개수

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

저번 뱀 문제에서 상하 좌우를 dx=[-1,0,1,0], dy=[0,1,0-1]로 푸는 것을 보았던 것 같습니다.
기준 좌표 주변을 탐색할 때 이미 탐색한 값을 바꿔줌으로써 중복해서 탐색하지 않는 것만 막아주고, dx,dy를 다음과 같이 지정한다면 index 위치를 쉽게 지정할 수 있습니다.
뭔가 이 아이디어가 안떠올라 항상 직접 다 입력했던 것 같네요..

이번 문제는 8방향이기 때문에 다음과 같이 정해줬습니다.

dx = [1, 1, 1, -1, -1, -1, 0, 0] dy = [0, -1, 1, 1, 0, -1, 1, -1]

while True:
    w,h=map(int,input().split())
    if w==0 & h==0: # 정지 조건
        break
    
    
    test_map=[] # 지도 만들기
    for i in range(h):
        row_input=list(map(int,input().split()))
        test_map.append(row_input)
    
    dx = [1, 1, 1, -1, -1, -1, 0, 0] # -1이면 앞, 1이면 뒤에 
    dy = [0, -1, 1, 1, 0, -1, 1, -1] # 1이면 아래 0 이면 같은 층 -1이면 위에 층 (중복해서 계산하지 않도록 2로 바꿔주기)
    # ex dx=-1,dy=0 => 앞에 칸, dx=1,dy=1 => 오른쪽 아래 칸
    que=[]
    count=0 # 섬의 개수 count
    for j in range(h):
        for k in range(w):
            if test_map[j][k] ==1: #처음 시작 육지
                que.append((j,k)) #육지에 방문하면 좌표 표시
                test_map[j][k]=2 # 방문한 곳은 2로 표시
                
                while que:
                    x,y=que[0]# 방문한 곳 출력
                    que.pop(0)
                    for l in range(8): #방향 탐색
                        x_=x+dx[l]
                        y_=y+dy[l]
                        if 0<=x_<h and 0<=y_<w:#땅 안에 있어야한다.
                            if test_map[x_][y_]==1:
                                que.append((x_,y_))
                                test_map[x_][y_]=2
                else:
                    count+=1 #육지가 끝났으므로 육지 수 +1
                    
    print(count)

1 1
0
0
2 2
0 1
1 0
1
3 2
1 1 1
1 1 1
1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
3
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
9
0 0