[BOJ]1189 컴백홈

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

1189번: 컴백홈

풀이

오늘 너덜너덜해진 멘탈로 인하여 다소 쉬운 문제를 풀기로 했다... 간단한 dfs문제인데 처음에는 한번 지나친 곳은 다시 가지 않는다길래 한 번 간 칸은 방문하지 않는다로 생각했지만, 그냥 단순히 방문처리 하면 되는 문제였다. 관건은 입력으로 주어지는 칸을 만약 시작점이 (0, 0), 도착점이 (R-1, C-1)로 한다면 T의 위치가 다르게 입력을 받으므로 시작점을 (R-1, 0), 도착지점을 (0, C-1)로 해야하는 점만 주의하면 되겠다.

import sys
input = lambda: sys.stdin.readline().rstrip()
def dfs(x, y, cnt):
    global count
    #print(road)
    visited[x][y] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        #print(nx, ny)
        if nx < 0 or ny < 0 or nx >= R or ny >= C:
            continue
        #print(0)
        if visited[nx][ny]:
            continue
        #print(1)
        if road[nx][ny] == 'T':
            continue
        #print(2)
        if nx == 0 and ny == C-1:
            if cnt+1 == K:
                count += 1
            continue
        #print(3)
        dfs(nx, ny, cnt+1)
    visited[x][y] = False
R, C, K = map(int, input().split())
road = [input()for _ in range(R)]
visited = [[False for _ in range(C)]for _ in range(R)]
count = 0
dx = [1, -1, 0,  0]
dy = [0, 0, 1, -1]
dfs(R-1, 0, 1)
print(count)