[Python] 1189번 컴백홈

✏️ 문제

 

 

문제 파악

한 방향으로 갈 수 있는 만큼 끝까지 갔다가 더 갈 곳이 없다면 이전 위치로 돌아가면서 한수의 집을 도착하는 모든 경로를 찾는 백트래킹을 사용하는 문제이다.

백트래킹 문제는 BFS와 DFS 둘 다 사용해서 풀 수 있지만 특징상 DFS로 푸는 것이 편하다.

한수는 상하좌우로 이동할 수 있으므로 방향 배열을 다음과 같이 정의했다.

d = [(1, 0), (0, 1), (0, -1), (-1, 0)]

 

그리고 깊이 탐색을 하다가 더 갈 곳이 없다면 이전 위치로 돌아가면서 들렀던 위치에 대한 방문을 안했다고 수정해야 하는데 그 이유는 현재 경로와 다른 경로로도 탐색해야 하기 때문이다.

visited[x][y] = 0

 

! 문제에서 한수의 위치는 왼쪽 아래, 한수의 집 위치는 오른쪽 아래라고 했으므로 무의식 중에 (0, 0), (r-1, c-1)로 주지 않도록 하자....

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 브루트포스 알고리즘
• 백트래킹

 

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

r, c, k = map(int, input().split())
graph = [list(input().strip()) for _ in range(r)] 
visited = [[0] * c for _ in range(r)] 
d = [(1, 0), (0, 1), (0, -1), (-1, 0)] 
num = 0 

def dfs(x, y, dis):
  global num

  if x == 0 and y == c-1:
    if dis == k:
      num += 1
    return

  visited[x][y] = 1

  for i in range(4):
    dx = x + d[i][0]
    dy = y + d[i][1]
     
    if 0 <= dx < r and 0 <= dy < c and not visited[dx][dy] and graph[dx][dy] != 'T':
      dfs(dx, dy, dis + 1)
   
  visited[x][y] = 0

dfs(r-1, 0, 1) 
print(num)

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS