[백준][Python] 1189 컴백홈

그래프, 브루트포스, dfs, 백트래킹 / 실버 1

⛺️

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

1189번: 컴백홈

 

 

내 풀이 (첫 번째)

def dfs(x, y, d):
    global ans

    if x == 0 and y == C - 1:
        count_T = 0
        for i in range(R):
            count_T += visited[i].count(True)
        if count_T == K - 1:
            ans += 1
            return
        
    if x < 0 or x >= R or y < 0 or y >= C:
        return
    
    if arr[x][y] == '.' and not visited[x][y]:
        visited[x][y] = True
        dfs(x-1, y, d + 1)
        dfs(x+1, y, d + 1)
        dfs(x, y-1, d + 1)
        dfs(x, y+1, d + 1)
        visited[x][y] = False


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

for i in range(R):
    arr[i] = list(input())

arr[0][C-1] = 'G'
dfs(R-1, 0, 1) # 현재 좌표, 현재 거리

print(ans)

 

 

코드 설명

 

집의 좌표(오른쪽 위)가 목적지임을 표시했다. (goal)

arr[0][C-1] = 'G'

 

dfs를 호출할 때는 현재 한수의 위치 좌표와 거리를 매개변수로 넣는다.

dfs(R-1, 0, 1) # 현재 좌표, 현재 거리

 

 

✔️ dfs 함수

 

현재 좌표가 목적지 좌표인 경우, 방문처리된 좌표의 개수를 센다.

개수가 K-1인 경우라면, 한수가 집까지 K 거리를 거쳐 도착했다는 것을 의미하므로, 정답 변수에 1을 증가시킨 뒤 종료한다.

cf) K-1인 이유는, 목적지 좌표는 방문처리되지 않기 때문이다.

if x == 0 and y == C - 1:
    count_T = 0
    for i in range(R):
        count_T += visited[i].count(True)
    if count_T == K - 1:
        ans += 1
        return

 

만약 현재 좌표가 범위를 벗어났다면, 바로 종료한다.

if x < 0 or x >= R or y < 0 or y >= C:
    return

 

현재 좌표가 이동할 수 있는 곳이며, 아직 방문하지 않은 곳이라면

방문 처리를 해준다.

그리고 dfs를 호출하며 현재 위치의 상하좌우를 모두 검사한다.

검사가 끝나고 나면, 방문 처리를 철회한다.

if arr[x][y] == '.' and not visited[x][y]:
    visited[x][y] = True
    dfs(x-1, y, d + 1)
    dfs(x+1, y, d + 1)
    dfs(x, y-1, d + 1)
    dfs(x, y+1, d + 1)
    visited[x][y] = False

 

⛺️

 

내 풀이 (두 번째)

def dfs(x, y, d):
    global ans

    if x == 0 and y == C - 1 and d == K:
        ans += 1
        return
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if 0 <= nx < R and 0 <= ny < C and arr[nx][ny] == '.':
            arr[nx][ny] = '!'
            dfs(nx, ny, d+1)
            arr[nx][ny] = '.'

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(R):
    arr[i] = list(input())

arr[R-1][0] = 'S'
dfs(R-1, 0, 1) # 현재 좌표, 현재 거리

print(ans)

 

 

코드 설명

 

출발점을 표시했다. (start)

arr[R-1][0] = 'S'

 

dfs를 호출할 때는 현재 한수의 위치 좌표와 거리를 매개변수로 넣는다.

dfs(R-1, 0, 1) # 현재 좌표, 현재 거리

 

 

✔️ dfs 함수

 

현재 좌표가 목적지 좌표이며 이동 거리가 K인 경우, 정답 변수에 1을 증가시킨 뒤 종료한다.

if x == 0 and y == C - 1 and d == K:
    ans += 1
    return

 

상하좌우를 검사하며 새 좌표가 범위 내에 있으면서 이동할 수 있는 곳이라면,

방문했다는 의미로 해당 좌표 값을 느낌표로 변경하였다.

dfs 호출 후, 값을 원래대로 돌려놓는다.

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

    if 0 <= nx < R and 0 <= ny < C and arr[nx][ny] == '.':
        arr[nx][ny] = '!'
        dfs(nx, ny, d+1)
        arr[nx][ny] = '.'

 

⛺️

첫 번째 풀이에서는 현재 좌표의 상하좌우를 검사할 때, 무조건 dfs를 호출하였고

두 번째 풀이에서는 새 좌표가 조건을 만족하는 경우에만 dfs를 호출하였다.

 

위: 두 번째 풀이 / 아래: 첫 번째 풀이