[백준] 1189. 컴백홈(python, 파이썬)

문제

1189. 컴백홈

📌 아이디어

문제에서 주어진 K 만큼 탐색을 한 다음에 도착 지점을 비교하면 되기 때문에 전형적인 백트래킹 유형이라는 것을 떠올릴 수 있었습니다.

1. DFS 탐색을 통해 상하좌우 4방향을 탐색합니다.
2. 방향이 선정되면 다음 칸으로 이동 후 유효성을 검사 후 다음 탐색으로 넘어갑니다.
3. 거리가 K가 되었다면, 올바른 도착 지점인지를 확인한 후 정답 처리를 진행합니다.

📌 코드

def dfs(i, j, k, v):
    global ans
    if k == K: # 주어진 거리와 일치하다면 도착점을 비교 후 정답 처리
        if (i, j) == (0, C-1):
            ans += 1
        return
    else:
    	# 상 하 좌 우 방향 탐색
        for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            ni = i + di
            nj = j + dj
            if 0 <= ni < R and 0 <= nj < C:
            	# 방문 처리 -> 다음 방향 탐색 -> 방문 해제
                if arr[ni][nj] == '.' and [ni, nj] not in v:
                    v.append([ni, nj])
                    dfs(ni, nj, k+1, v)
                    v.pop()

R, C, K = map(int, input().split())
arr = [list(input()) for _ in range(R)]
ans = 0

dfs(R-1, 0, 1, [[R-1, 0]])

print(ans)

피드백 및 개선점은 댓글을 통해 알려주세요😊