[백준] 16946번 벽 부수고 이동하기4 - 파이썬/DFS

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

1차 풀이

import sys
sys.setrecursionlimit(10**6)

N,M = map(int,input().split())

graph = [ list(map(int,input())) for _ in range(N) ]


def dfs(x,y,visited):

    global cnt
    cnt+=1
    visited[x][y]=True

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

    for i in range(4):

        nx = x+dx[i]
        ny = y+dy[i]

        if 0<=nx<N and 0<=ny<M:
            if not visited[nx][ny] and graph[nx][ny]==0:
                dfs(nx,ny,visited)

ans = [[0] * M for _ in range(N)]

for i in range(N):
    for j in range(M):
        if graph[i][j]==1:
            visited = [[False] * M for _ in range(N)]
            cnt = 0
            dfs(i,j,visited)
            ans[i][j]=cnt

print(ans)

전체 배열을 순회하면서 1 -> 0으로 바꾸고 DFS를 하는 방식으로 풀었는데

visited 를 반복마다 생성해서그런지 시간초과로 통과x

2차 풀이

import sys
sys.setrecursionlimit(10**6)

N,M = map(int,input().split())

graph = [ list(map(int,input())) for _ in range(N) ]

ans_graph = [[0] * M for _ in range(N)]
area_dict=dict() # 구역 정보를 담은 딕셔너리

def dfs(x,y,visited,area):
    global cnt
    cnt+=1
    visited[x][y]=True
    graph[x][y]=area

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

    for i in range(4):

        nx = x+dx[i]
        ny = y+dy[i]

        if 0<=nx<N and 0<=ny<M:
            if not visited[nx][ny] and graph[nx][ny]==0:
                dfs(nx,ny,visited,area)

visited = [[False] * M for _ in range(N)]

area = 2

for i in range(N):
    for j in range(M):
        cnt=0 # 구역의 크기
        if graph[i][j]==0:
            dfs(i,j,visited,area)
            area_dict[area] = cnt
            area +=1

for i in range(N):
    for j in range(M):
        ans_list = [] # 인접 구역의 이름
        if graph[i][j]==1:
            ans_graph[i][j] +=1
            ans = 0
            dx = [1, -1, 0, 0]
            dy = [0, 0, 1, -1]

            for k in range(4):

                nx = i + dx[k]
                ny = j + dy[k]

                if 0 <= nx < N and 0 <= ny < M:
                    if graph[nx][ny] >1:
                        ans_list.append(graph[nx][ny])

            ans_list = list(set(ans_list))
            for t in ans_list:
                ans_graph[i][j]+=area_dict[t]

            ans_graph[i][j] = ans_graph[i][j] % 10


for i in ans_graph:
    print(''.join(map(str,i)))

1. graph 에서 0의 구역을 나누어서 2부터 넣어줌. (area라는 변수가 구역의 이름)

graph는 아래처럼 변한다.

11001          11221
00111   ->     33111
01010          31415
10101          16171

2. 구역의 크기를 구해서 이름과 함께 딕셔너리에 넣어줌. (area_dict)

3. graph를 순회하면서 graph[i][j]가 1일 경우 인접한 구역의 이름을 리스트에 담는다. (ans_list) 이때, 중복 제거를 위해 집합을 이용한다.

4. 인접 리스트를 반복하면서 딕셔너리에서 크기값을 불러와 더해준다.