[solved.ac 실버1] 1189_컴백홈 (파이썬, 브루트포스, 백트래킹)

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

문제

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

      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인 가짓수를 구하는 것이다.

입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력

첫 줄에 거리가 K인 가짓수를 출력한다.

예제

---

나의 풀이

문제의 조건을 면밀히 살펴보자. 시작 위치는 왼쪽 아래, 도착 위치는 오른쪽 위이다. 그리고 문제의 예시를 보면 시작 위치도 카운트하는 것을 알 수 있다.

만약 6번 만에 도착 지점까지 갈 수 있다면 하나씩 카운트를 해주면 된다. 백트래킹을 통한 브루트포스로 할 수 있다.

백트래킹 문제를 풀어봤다면 쉽게 풀 수 있다.

n, m, K = map(int, input().split())
graph = [list(input()) for _ in range(n)]
answer = 0

def rec_fun(x, y, k):
    global answer
    if k == K:
        if (x, y) == (0, m - 1): answer += 1
    else:
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] != 'T':
                graph[nx][ny] = 'T'
                rec_fun(nx, ny, k + 1)
                graph[nx][ny] = '.'

graph[n - 1][0] = 'T' # 시작 지점 방문 처리
rec_fun(n - 1, 0, 1)
print(answer)

다음 위치가 T 가 아닐 때 이동할 수 있으며 이동했다면 해당 위치를 T로 만들어 재방문하지 않도록 만들고, 탐색이 완료됐다면(재귀를 빠져 나온 경우) T로 만든 것을 다시 .으로 바꿔주면 된다.

여기서 주의할 점은 시작 지점도 방문 처리(T로 변경) 해야 한다는 것이다.

채점 결과