백준 1189번 파이썬

문제 링크

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

1189번: 컴백홈

 

시간 제한 / 메모리 제한

2 초

128 MB

 

문제

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

      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인 가짓수를 출력한다.

예제 입력

3 4 6
....
.T..
....

예제 출력

4

 

문제 풀이를 위해 생각한 것

1. DFS로 모든 경우의 수를 탐색하며, 출발 지점으로부터의 거리 변수를 +1 한다.
2. 목적지에 도달했을 때 거리 변수가 k이면 전역변수 cnt를 +1 한다.

-------------------------------------------------------------------------------

1. 문제 이해를 잘못해서 방문처리를 안 했더니 메모리 초과가 됐다.
2. 한 경로에서 같은 곳을 방문하지 않도록(무한루프) 경로 상 방문 지점을 dfs의 인자로 전달해야 한다.

 

사용한 자료구조 / 알고리즘

2차원 배열 / DFS(재귀)

 

풀이 코드

import sys
sys.setrecursionlimit(10**6)
r, c, k = map(int, input().split())
board = [list(input()) for _ in range(r)]
dx = (1, -1, 0, 0)
dy = (0, 0, 1, -1)
_dict = {}


def dfs(x, y, d, visited):
    visited.append([x, y])
    if x == 0 and y == c - 1:
        if d in _dict:
            _dict[d] += 1
        else:
            _dict[d] = 1
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < r and 0 <= ny < c and board[nx][ny] != 'T' and [nx, ny] not in visited:
            dfs(nx, ny, d + 1, visited + [nx, ny])


dfs(r-1, 0, 1, [])
print(_dict[k] if k in _dict else 0)

 

시간 복잡도 분석

O(3^N).

매 선택지에는 경로 상 직전에 방문한 곳을 제외한 3개의 선택지가 있다.

 

문제에서 중요한 부분

DFS를 수행할 때 전체 지도에서의 방문처리가 아닌 해당 경로 내에서의 방문처리를 해야 했다.

비슷한 문제에 좀 더 숙달되어야 로직이 떠오를 것 같다.