[백준 11889번] 컴백홈 - 파이썬

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

💡문제 분석 요약

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

 

💡알고리즘 설계

이번 문제는 문제를 이해하는게 오래 걸려서 이해하기 쉽게 예제에서 이동한 경로를 피그마를 이용해 대략적으로 그려보았다.

그림처럼 한수가 맨 왼쪽 아래에 있고, 집은 맨 오른쪽 위에 있다, 여기서 T를 피해 여러가지 방법으로 집을 도착하는데, 이 때 이동 거리가 K인 경우의 수를 모두 세면 된다.

예제에서는 이동 가능한 경우가 위 그림처럼 4가지가 있다.

한수가 출발하는 위치와 도착하는 위치도 모두 포함해 이동 거리로 센다.

(개인적으로 이동 거리보다는 방문한 칸의 수라고 생각하면 더 이해가 쉬울 것 같다.)

 

 

1. 출발 위치에서, 주변 4방향이 이동 가능한 방향인지 확인한다 (위치가 범위 내고, ground[ny][nx]='.'인지 확인)

2. 이동 가능 하다면, 이동하기 전 그 위치의 값을 T로 바꾸어 방문했음을 표시하고, 재귀함수에 이동거리+1, 새로운 위치를 파라미터로 전달하며 호출한다. 그 다음 다시 위치의 값으 '.'으로 바꿔 다른 경우에 다시 방문할 수 있게 한다.

3.이동 거리가 K고, 현재 위치가 목적지라면 경우의 수를 저장하는 변수 answer에 1을 더한다.

4. 모든 탐색이 끝나면 answer을 출력한다.

 

 

💡코드

import sys
input = sys.stdin.readline

R,C,K=map(int,input().split())

ground=[ list(input().rstrip()) for _ in range(R) ] 
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
#북 동 남 서

answer=0
def search(count, x, y):
    global answer
    if count==K and x==C-1 and y==0:
        answer+=1
    else:
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=nx<C and 0<=ny<R and ground[ny][nx]=='.':
                ground[ny][nx]='T'
                search(count+1, nx, ny)
                ground[ny][nx]='.'

ground[R-1][0]='T'
search(1, 0, R-1)
print(answer)

#한수: 왼쪽 아래 (0,R-1) 목적지:오른쪽 위 (C-1,0)

 

💡 느낀점 or 기억할 정보

무난한 DFS 문제였다. 문제 이해하기가 어려웠는데 다시 보니 왜 어려웠는지 모르겠다. 집중하지 않고 대충 읽어서 그런거겠지..?

다른 분들의 코드를 찾아보니 대부분 ground[x][y]로 쓰시던데, 이렇게 해도 문제는 없지만 전체 ground를 출력하면 위치가 반대로 나와 ground[y][x]를 고집하는 편이다. 항상 테이블을 전체적으로 봐야 이해하는게 쉬워서.. ㅎ