[백준] 1189 - 컴백홈

문제

백준 1189번 컴백홈

문제 링크 : https://www.acmicpc.net/problem/1189

 

 

문제 풀이

목적 : 한수가 집까지 도착하는 모든 경우의 수 중 거리가 K인 가짓수를 구하는 것

모든 경로를 찾기 위해 백트래킹과 DFS를 이용할 수 있다. 

백트래킹 : 백트래킹은 모든 가능한 경로를 탐색하되, 중간에 조건에 맞지 않다면 탐색을 중단하고 되돌아가는 방식이다. 이 문제에서는, 한수의 위치가 집일 때 탐색을 중단하고 리턴하며, 리턴 이후의 코드에서는 visited을 다시 False로 되돌려 다른 경로를 탐색할 수 있도록 하였다.

DFS : 깊이 우선 탐색으로, 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하기 때문에, 최적의 경로가 아닌 모든 경로를 탐색할 수 있다. 함수의 재귀를 통해 한수가 집에 다다를 때까지 깊이 우선 탐색을 진행한다.

함수 dfs(x,y,depth) : DFS를 수행하는 함수로써, visited 배열을 사용해 백트래킹 알고리즘을 진행하고, 한수의 위치 (x,y)가 집(0,c-1) 일 경우 dist 배열에 지금까지 탐색한 경로의 거리를 추가하고 리턴하여 다음 경로 탐색을 진행한다.

배열 dist : 모든 경로의 거리를 저장하며, 이후 dist.count(k)를 통해 거리가 k인 요소의 수를 출력한다.

 

코드

r,c,k=map(int,input().split(' '))
board=[list(map(str,input().rstrip())) for _ in range(r)]

d=[(0,1),(0,-1),(1,0),(-1,0)]
visited=[[False for _ in range(c)] for _ in range(r)]
visited[r-1][0]=True
dist=[]
def dfs(x,y,depth):
  if x==0 and y==c-1:
    dist.append(depth)
    return
  for i in range(4):
    a=x+d[i][0]
    b=y+d[i][1]
    if 0<=a<r and 0<=b<c and not visited[a][b] and board[a][b]=='.':
      visited[a][b]=True
      dfs(a,b,depth+1)
      visited[a][b]=False
dfs(r-1,0,1)
print(dist.count(k))