[백준] 9944 : NxN 보드 완주하기 - Python

문제

nxn 보드, 각 칸은 빈칸 또는 장애물
보드 위에 공 하나 놓아야 함.
상하좌우 중 방향 하나 고른 후 그 방향으로 계속 이동시킨다
공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속 이동
더이상 이동할 수 없을 때 끝난다. -> 모든 빈칸을 방문한 적이 있어야 함
모든 칸을 방문하기 위한 이동 횟수의 최솟값

시작위치는 어디든 상관없음

내 코드

import sys
sys.stdin = open("input.txt", "rt")

# nxm 보드 완주
# nxm 보드, 각 칸은 빈칸 또는 장애물.
# 상하좌우 방향 중 방향 하나 선택해서 해당 방향으로 계속 이동시켜야함.
# 공은 장애물, 보드의 경계, 이미 지나갔던 칸을 만나기 전까지 계속 이동.
# 공이 더 이상 이동할 수 없을 때 끝.
# 이때 공이 모든 빈칸을 방문한 적이 있어야 한다.
# 이동 횟수의 최솟값 구하기

# 문제 해결
# 빈칸만 이동하되, 이동할 때마다 방문체크 해줘야 함.
# 빈칸 어디에서든 시작 가능.


blank = "."
wall = "*"

dx = [-1,0,1,0]
dy = [0,1,0,-1]
def isInner(x,y):
    return 0<=x<n and 0<=y<n

def DFS(x,y,dir, now_cnt, level): # 현재 위치, 방향, 현재까지의 방문 개수, 현재 레벨
    global res
    if level >= res:
        return # 최소값을 구해야 하므로

    if now_cnt == cnt: # 모두 방문
        res = min(res, level)
    else: # 그게 아니라면 계속 이동
        nx = x + dx[dir]
        ny = y + dy[dir]
        if (isInner(nx,ny)
                and g[nx][ny] == blank
                and not visited[nx][ny]): # 빈칸, 방문전, 내부인 경우에 이동 가능
            visited[nx][ny] = True
            DFS(nx,ny,dir, now_cnt + 1, level)
            visited[nx][ny] = False # 백트랙킹 시 원상복구
        else: # 그 경우가 아니라면 방향 전환 -> 방향 전환도 현재 위치에서 현재 방향 제외 3 방향 모두 시도해야함
            for i in range(1,4):
                direction = (dir + i) % 4
                nx = x + dx[direction]
                ny = y + dy[direction]
                if (isInner(nx,ny)
                        and g[nx][ny] == blank
                        and not visited[nx][ny]):
                    visited[nx][ny] = True
                    DFS(nx,ny,direction, now_cnt + 1, level + 1)
                    visited[nx][ny] = False



case = 1
while True:
    try:
        n,m = map(int, input().split())
        g = [list(map(str,input())) for _ in range(n)]

        cnt = 0
        for i in range(n):
            for j in range(m):
                if g[i][j] == blank:
                    cnt += 1 # 빈칸 개수

        res = int(1e9)
        for i in range(n):
            for j in range(m):
                if g[i][j] == blank:
                    for d in range(4):
                        visited = [[False] * m for _ in range(n)]
                        visited[i][j] = True
                        DFS(i,j,d,1,1)

        if cnt == 1:
            print(f"Case {case}: {0}")
        elif res == int(1e9):
            print(f"Case {case}: {-1}")
        else:
            print(f"Case {case}: {res}")
        case += 1
    except EOFError:
        break

코멘트

해당 문제 시간 복잡도가 N^4가 아니라, N*4인 이유에 대해 주목해야 한다.
각 시작점에서 4방향으로 시작한다. -> O(4)
한 방향으로 이동할 때 해당 방향으로 계속 이동. 이동이 불가능할 때만 다른 방향으로 전환한다. 이는 매 스텝마다 4방향을 모두 탐색하는 것이 아니라, 현재 방향으로 더 이상 갈 수 없을 때만 새로운 방향을 선택한다.

단계를 구할 때 한가지 주의할 점은 공이 시작점에 놓였을 때 사방이 장애물이면 이동하지 않기 때문에 단계는 0이된다.

이동을 해야 단계가 추가된다는 점을 간과했다. 실수하지 말자 !!

DFS시에 방문체크하는 거 잊지말자 !!