DFS 적용 - 경로 가짓수 구하기

Chooooo·2023년 2월 8일

알고리즘 활용하는 문제 유형들

목록 보기

11/33

경로 가짓수 구하기

미로탐색(DFS)

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

▣ 입력설명
7*7 격자판의 정보가 주어집니다.

▣ 출력설명
첫 번째 줄에 경로의 가지수를 출력한다.

▣ 입력예제 1
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0

▣ 출력예제 1
8

위 문제로 경로 가짓 수 이해하기

해당 문제를 보면 출발점에서 도착점까지 가는데 갈 수 있는 방법의 수를 구하는 문제이다.

최단거리를 구하라고 했으면 BFS로 풀었으면 됐지만, 경로의 수를 구하는 것이기에 출발점부터 도착점까지 끝까지 파고드는 DFS를 이용하는 것이 맞다.
똑같이 상하좌우 방향벡터를 사용하고, 현재위치에서 상하좌우 살피면서 도착점까지 가면 카운트 + 1
백트랙킹 시 기존 체크 표시 원상복구. 풀었던 유형 그대로 문제에 적용하면 된다 !!

⚽ 코드를 보며

import sys
# sys.stdin = open("input.text", "rt")
from collections import deque

g = [list(map(int, input().split())) for _ in range(7)]
#0으로만 이동해야함.

dq = deque()
dis = [[0] * 7 for _ in range(7)]
dq.append((0,0)) #시작위치 삽입하고 시작
g[0][0] = 1 #시작점 방문 표시 후 시작
dx = [1,-1,0,0]
dy = [0,0,1,-1]

cnt = 0

def DFS(x,y):
    global cnt

    if x == 6 and y == 6:   #도착지점.
        cnt += 1
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0<=nx<7 and 0<=ny<7:  #경계선 안에 있는지 확인.
                if g[nx][ny] == 0: #방문 전
                    g[nx][ny] = 1
                    DFS(nx,ny)
                    g[nx][ny] = 0 #백트랙킹 시 원상복구

g[0][0] = 1 #시작점은 방문처리.
DFS(0,0)
print(cnt)

해당 코드만 봐도 DFS 돌리면서 도착점 도착 시 탈출조건. 그게 아니라면 현재위치에서 가지 뻗어나가기(상하좌우 4가지) + 중복 체크 확인 + 백트랙킹 시 원상복구.

그대로 풀면 된다.

⚽ 똑같은 유형의 다른 문제

등산경로(DFS)

등산을 매우 좋아하는 철수는 마을에 있는 뒷산에 등산경로를 만들 계획을 세우고 있습니다. 마을 뒷산의 형태를 나타낸 지도는 N*N 구역으로 나뉘어져 있으며, 각 구역에는 높이가 함께 나타나 있습니다.
N=5이면 아래와 같이 표현됩니다.

어떤 구역에서 다른 구역으로 등산을 할 때는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동할 수 있도록 등산로를 설계하려고 합니다. 등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳입니다. 출발지와 목적지는 유일합니다.
지도가 주어지면 출발지에서 도착지로 갈 수 있는 등산 경로가 몇 가지 인지 구하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 N(5<=N<=13)주어지고, N*N의 지도정보가 N줄에 걸쳐 주어진다.

▣ 출력설명
등산경로의 가지수를 출력한다.

▣ 입력예제 1
5
2 23 92 78 93
59 50 48 90 80
30 53 70 75 96
94 91 82 89 93
97 98 95 96 100

▣ 출력예제 1
5

import sys
# sys.stdin = open("input.text", "rt")
from collections import deque

n = int(input())
g = [list(map(int, input().split())) for _ in range(n)] #nxn 2차원 리스트

min_data = 24242424
max_data = -24242424
x,y = 0,0
for i in range(n):
    for j in range(n):
        if g[i][j] < min_data:
            min_data = g[i][j]
            x,y = i,j #시작 위치
        if g[i][j] > max_data:
            max_data = g[i][j]


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

ch = [[0] * n for _ in range(n)] #중복 체크
ch[x][y] = 1 
cnt = 0
def DFS(x,y):
    global cnt
    if g[x][y] == max_data: #목적지
        cnt += 1
    else: #아직 도착전이면 계속 가지 뻗기
        for i in range(4):
            nx = x + dx[i]
            ny = y  +dy[i]

            if 0<=nx<n and 0<=ny<n:
                if ch[nx][ny] == 0: #방문 전
                    if g[nx][ny] > g[x][y]: #현재 위치보다 높은 곳으로
                        ch[nx][ny] = 1
                        DFS(nx,ny)
                        ch[nx][ny] = 0 #백트랙킹
    
DFS(x,y)
print(cnt)