[백준1189] / 컴백홈 - DFS, 백트래킹

 

백준1189

 

 

푼 날짜 : 2024.10.30

푼 문제 : [1189] / 컴백홈

사용한 언어 : python

알고리즘 : DFS/백트래킹

 

 

접근 방식 :

DFS로 탐색하며 K만큼 이동한 위치가 목적지라면 카운트 해주는 방식으로 구현했다.

 

 

코드 : 

import sys

R, C, K = map(int, sys.stdin.readline().split())
graph_ = []
for _ in range(R):
    row = list(sys.stdin.readline().rstrip())
    graph_.append(row)

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

visited = [[0 for _ in range(C)] for _ in range(R)]
ans = 0

def DFS(v, now):
    global ans
    
    # K번 이동을 체크하기 위함
    if now == K-1:
    	# 도착지에 도달했다면 가짓수 증가
        if v[0] == 0 and v[1] == C-1: ans += 1
        # 리턴하여 더 이상 탐색하지 않도록 종료
        return

    for i in range(4):
        ny, nx = v[0]+dy[i], v[1]+dx[i]
        if 0<=ny<R and 0<=nx<C:
            if graph_[ny][nx] != 'T' and not visited[ny][nx]:
                visited[ny][nx] = 1 # 방문처리
                DFS((ny, nx), now+1)
                visited[ny][nx] = 0 # 되돌아 왔으므로 방문처리 해제

# 왼쪽 하단에서 시작
visited[R-1][0] = 1
now = 0
DFS((R-1, 0), now)
print(ans)

 

 

백트래킹 연습 열심히 해야지~