[Python] DFS 문제 풀이 정리

DFS 정복하기.

물론 이분탐색이나 BFS도 있지만 내가 느끼기에 상대적으로 많이 보이는 건 DFS이다. 그래서 DFS를 중심으로 문제 연습!

 

---

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

2468번: 안전 영역

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

n = int(input()) # 2차원 행/열
# visited= [[False]*(n) for _ in range(n)]
maxNum = 0 # 최대 높이 저장
arr = [] # 높이 배열
# print(visited)
for i in range(n):
    arr.append(list(map(int, input().split())))
    for j in range(n):
        if arr[i][j] > maxNum:
            maxNum = arr[i][j] 

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

def DFS(x, y, h):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0<=nx<n) and (0<=ny<n) and not visited[nx][ny] and arr[nx][ny]>h:
        # 다음에 이동할 장소가 유효하고, 방문하지 않았으며, h보다 높이가 높을 때!
            visited[nx][ny]=True
            DFS(nx,ny,h)



ans = 1
for h in range(maxNum): # 최대 높이 계속 늘리기
    visited= [[False]*(n) for _ in range(n)] # 강수량이 바뀔때마다 안전영역을 다시 계산해야 하므로 안에다가 선언!
    count = 0 # DFS 횟수인 count도 마찬가지. 안전 영역의 수가 된다.
    for i in range(n):
        for j in range(n):
            if arr[i][j] > h and not visited[i][j]:
                count += 1
                visited[i][j] = True
                DFS(i, j, h)
    ans = max(ans, count) # 최댓값 저장

print(ans)

• 시뮬레이션 + DFS 문제!
• 상하좌우를 바꿔가며 만약 방문하지 않았고, 상하좌우 이동이 가능하며 최대 눌 높이가 높은 경우 DFS를 실행(탐색
• 따라서 물 높이는 0부터(비가 안오는 경우) 최대 높이 -1까지(최대 높이면 안전 영역은 0이다. 최댓값을 찾아므로 탐색 X)까지 물 높이 h를 바꿔가며 안전영역의 수를 탐색한다.
• 안전영역의 수(count)는 DFS가 실행된 횟수이다.
• count의 최댓값을 찾는다. 따라서 물 높이를 바꿀때마다(for문이 실행될때마다) count와 visited배열(스택)은 초기화 시켜줘야 함.

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

4963번: 섬의 개수

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

while True:
    w,h = map(int, input().split()) # 너비, 높이(열, 행)==(가로, 세로)
    if w==h==0:
        break
    arr=[]
    visited=[[False]*w for _ in range(h)]
    for i in range(h):
        arr.append(list(map(int, input().split()))) # 지도. 1은 땅, 0은 바다.

    dx = [0 ,0, 1, -1, 1, 1, -1, -1] # 상하좌우대각선
    dy = [1, -1, 0 ,0, 1, -1, 1, -1]

    def DFS(x, y): # 가로, 세로로 입력 받음
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            # print(nx, ny)
            if (0<=nx<w) and (0<=ny<h) and not visited[ny][nx] and arr[ny][nx]==1:
            # 다음에 이동할 장소가 유효하고, 방문하지 않았고, 다음 장소가 땅이면!
                # print(ny, nx)
                visited[ny][nx]=True
                # print(visited)
                DFS(nx, ny) 
            

    count = 0
    for i in range(h):
        for j in range(w):
            if not visited[i][j] and arr[i][j]==1: # 방문하지 않았고 땅이면
                visited[i][j] = True
                count += 1
                DFS(j,i)

    print(count)

• 대각선까지 추가된 DFS 문제. 어렵지는 않다.
• 내가 틀렸던 점은 가로, 세로를 생각 없이 넣은 것때문이다...
  • 가로==너비(w)==열==j==x
  • 세로==높이(h)==행==i==y
• DFS 입력은 가로 위치, 세로위치로 입력 받는다. 대신 다른 배열들을 접근할 때는 [행][열] 인덱스로 접근하므로 반대로 작성해줘야 함을 잊지 말자..!

---

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

2583번: 영역 구하기

for _ in range(k): # 영역 분리!
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y2, y1, -1):
        for j in range(x1, x2):
            visited[m-i][j]=True

• 첫번째로 어려웠던 분리할 구역 입력 받기!
• 왼쪽 아래를 0,0으로 가정하므로 잘 생각해서 인덱스를 잘 고려해서 입력받는다.

# 틀린 답

answer = [] # 넓이 저장 리스트
dx = [0 ,0, 1, -1,] # 상하좌우
dy = [1, -1, 0 ,0]

def DFS(x, y, area):
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<n and 0<=ny<m and not visited[ny][nx]:
            visited[ny][nx]=True
            area += 1
            DFS(nx, ny, area)
    if len(answer)<count: # 넓이 저장. 단, 넓이는 계속 작아지므로 처음 return하는 값만 저장
        answer.append(area)
    

count = 0

for i in range(m):
    for j in range(n):
        area = 0
        if not visited[i][j]:
            count += 1
            area += 1
            visited[i][j] = True
            DFS(j, i, area)

• area를 어떻게 전달하는가...젤 어려웠다.
• DFS안에서 DFS를 호출하는 경우를 잘 고려해서 area값을 전달해야 한다. 

# 정답

def DFS(x, y, area):
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<n and 0<=ny<m and not visited[ny][nx]:
            visited[ny][nx]=True
            area = DFS(nx, ny, area+1)
    return area
    

count = 0

for i in range(m):
    for j in range(n):
        area = 0
        if not visited[i][j]:
            count += 1
            area += 1
            visited[i][j] = True
            answer.append(DFS(j, i, area))   
            

print(count)
print(*(sorted(answer)))

• DFS에서 DFS를 다시 호출하려면 저렇게 함수 안에서 직접 수를 더한 후 전달해야 한다.
• 아니면 전역 변수로 선언해서..area값을 함수에서 공통적으로 다룰 수 있도록 한다.

---

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

2644번: 촌수계산

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

n = int(input())
arr = [[] for _ in range(n+1)]
num1, num2 = map(int, input().split()) # 구해야 하는 촌수
visited = [False]*(n+1)
result = []

for _ in range(int(input())):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

def DFS(v, k): # k는 촌수
    k+=1 # 촌수 +1
    visited[v] = True
    if v == num2:
        result.append(k)
    for i in arr[v]:
        if not visited[i]:
            DFS(i, k)



DFS(num1, 0)
if len(result)==0:
    print(-1)
else:
    print(result[0]-1)

• 처음에는 result 함수에 방문하는 정점을 순서대로 저장하고 그 간격을 출력하려 했다.
• 그런데 그러면 동일한 촌수(2촌)를 인식하지 못하므로 폐기...깊이가 깊어질 때 1을 추가하는 코드로 구현해야 한다.
• DFS를 호출할때마다 촌수는 +1이 된다.
• 또한 1부터 시작하는 것이 아닌, num1부터 시작하므로 거꾸로 올라갈때도 계산이 가능해진다.

---

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

1926번: 그림

import sys
sys.setrecursionlimit(10000000) # 100000 는 recursion error
input=sys.stdin.readline

n, m = map(int, input().split()) # 세로, 가로
arr= []
visited = [[False]*m for _ in range(n)]

for _ in range(n):
    arr.append(list(map(int, input().split())))

dx = [0,0,-1,1]
dy = [-1,1,0,0]
num1 = 0 # 개수
num2 = 0 # 넓이
def DFS(x, y, k): # 가로,세로, 넓이
    visited[y][x]=True
    for i in range(4):
        nx = x +dx[i]
        ny = y +dy[i]
        if 0<=nx<m and 0<=ny<n and not visited[ny][nx] and arr[ny][nx]==1:
            k = DFS(nx, ny, k+1)
    return k

for i in range(n):
    for j in range(m):        
        if not visited[i][j] and arr[i][j]==1:
            num1 += 1
            num2 = max(num2, DFS(j, i, 1))

print(num1)
print(num2)

• 그림의 갯수(num1)는 새로운 DFS를 돌릴 때마다 +1 해주기.
• 그림의 최대 넓이(num2)는 DFS를 돌릴 때 넓이(k)를 +1씩 하며 반복하고, 끝나면 num2와 비교하여 최댓값을 저장한다.
• 100000는 recursive error가 난다. 추가해주었음.

---

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

1325번: 효율적인 해킹

# 내 풀이(DFS)
import sys
sys.setrecursionlimit(10000000) 
input=sys.stdin.readline

n, m = map(int, input().split())
arr= [[] for _ in range(n+1)]
visited = [0]*(n+1) # False보다 int형이 빠르다함ㄴ

for _ in range(m):
    a, b = map(int, input().split())
    # arr[a].append(b)
    arr[b].append(a)

def DFS(v, k): 
    for i in arr[v]:
        if not visited[i]:
            visited[i]=1
            k = DFS(i, k+1)

    return k

answer = []

for i in range(1, n+1):
    visited = [0]*(n+1)
    if not visited[i]:
        visited[i]=1
        answer.append((i, DFS(i, 1)))
    
answer.sort(key = lambda x: (-x[1], x[0])) # 두번째 원소(해킹 가능한 수)는 내림차순, 컴퓨터 번호는 오름차순

# 난 못풀었다

from collections import deque
import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, input().split())
    graph[B].append(A)

# bfs
ans = []
for i in range(1, N+1):
    visited = [False]*(N+1)
    queue = deque([i])
    visited[i] = True
    
    cnt = 1
    while queue:
        x = queue.popleft()
        for j in graph[x]:
            if not visited[j]:
                visited[j] = True
                queue.append(j)
                cnt += 1
    ans.append(cnt)

max_cnt = max(ans)
for i in range(N):
    if ans[i] == max_cnt:
        print(i+1, end=" ")

• DFS로 풀면 시간/메모리 초과가 나는 문제. 왜죠?
• 또 위와 같이 BFS로 풀더라고 Python은 너무 느려서 안된다. PyPy로 제출해야 함.
• BFS로 푸는 법도 까먹지 말고...비록 틀렸지만 이 문제는 단방향 연결리스트 여서 정리하고 싶었다. 계속 안나오더라.

---

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

1743번: 음식물 피하기

import sys
sys.setrecursionlimit(10000000) 
input=sys.stdin.readline

n, m, k = map(int, input().split()) # 세로, 가로, 음식물 개수
arr = [[0]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]

for _ in range(k):
    a, b = map(int, input().split())
    arr[a-1][b-1] = 1

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

def DFS(x, y, num):
    visited[y][x] = True
    for i in range(4):
        nx = x +dx[i]
        ny = y +dy[i]
        if 0<=nx<m and 0<=ny<n and arr[ny][nx]==1 and not visited[ny][nx]:
            num = DFS(nx, ny, num+1)
    return num

max_num = 0
for i in range(n):
    for j in range(m):
        if not visited[i][j] and arr[i][j]==1:
            max_num=max(max_num, DFS(j,i,1))

print(max_num)

• 좌표가 (1,1) 부터 시작하는 것을 잊지 말자. 인덱스로 변환하기 위해 -1씩 해서 좌표를 저장했다.

---

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

2210번: 숫자판 점프

import sys
sys.setrecursionlimit(10000000) 
input=sys.stdin.readline

arr = []
# visited = [[0]*5 for _ in range(5)]
answer = []

for _ in range(5):
    arr.append(list(map(str, input().split())))

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

def DFS(x, y, num):
    # visited[y][x] = True
    if len(num)==6:
        if num not in answer:
            answer.append(num)
        return
    for i in range(4):
        nx = x +dx[i]
        ny = y +dy[i]
        if 0<=nx<5 and 0<=ny<5:
            DFS(nx, ny, num+arr[ny][nx])

for i in range(5):
    for j in range(5):    
        DFS(j,i,arr[i][j])

print(len(answer))

• 되돌아갈 수 있다. 즉 visited를 판별하지 않아도 돼서 더욱 간단했던 문제. 대신 DFS를 돌면서 문자를 더해주며 문자열을 완성시켜 나가야 한다.
• 문자열의 길이가 6이되면 멈추고 판별 후 답 리스트에 넣기. 출력은 리스트의 길이.
• 브루트 포스 알고리즘인 만큼 입력도 작아서 생각할게 없다 ㅎㅎ

---

# 회고

 

DFS를 하루종일 풀었다.

이번에는 실버 위주로 풀었는데...조금만 더 연습하고 골드도 해봐야지...

DFS를 잘 응용해서 DFS가 실행된 횟수/DFS 내부 변수 추가 등등 DFS 자체는 어렵지 않은데 응용 생각하는데 꽤 걸린 문제들이 있었다.

개인적으로 풀면서 양방향/단방향을 생각해보고 싶었는데 한문제뿐이라 아쉽다. 실버라 그런가?