[Python / BOJ 9944] NxM 보드 완주하기

 

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

9944번: NxM 보드 완주하기

 

 

 

0. 문제

N×M 보드 위에서 공을 가지고 할 수 있는 게임이 있다. 공은 다음과 같은 방식으로 1단계씩 움직인다.

• 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다.
• 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다.

게임은 공이 더 이상 이동할 수 없을 때 끝난다. 이 때, 모든 빈 칸을 공이 방문한 적이 있어야 한다.

모든 빈 칸을 방문할 수 없다면 최소 이동 횟수는 -1이다. 가능한 이동 경로의 수는 1,000,000개를 넘지 않는다.

10 단계 만에 모든 칸을 방문

 

 

 

1. 아이디어

문제를 풀기 위해 다음과 같은 요소를 생각해야 한다.

1. 한 지점에서 공이 어느 방향으로 이동해야 하는가?
   • 알 수 없다. 상, 하, 좌, 우 모든 방향으로 이동하는 것을 고려해야 한다.
2. 공은 어디에서 출발해야 하는가?
   • 특정 위치에서만 출발해도 되는 경우 대개 구석(edge) 위치이다. 하지만 해당 경우 모든 케이스를 커버하지 못한다.
   • 따라서 모든 위치에서 출발하는 경우를 살펴보아야 한다.

이제 공이 이동하는 방향과 시작점을 정할 수 있게 되었으므로 DFS 탐색을 하면 된다.

 

 

 

 

 

2. 구현

# 위 왼 아래 오
dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]


def go_or_back(start, d, flag, end=None):
    nr, nc = start
    next_start = (0, 0)

    # 범위 안에 있으면
    while 0 <= nr < R and 0 <= nc < C:
        # flag = 1 (go): 이동할 수 있으면 방문 체크
        if flag and (IN[nr][nc] == '.'):
            IN[nr][nc] = 'O'
            next_start = (nr, nc)
        # flag = 0 (back): 이미 방문 체크 되어있으면 방문 풀기
        elif (not flag) and (IN[nr][nc] == 'O'):
            IN[nr][nc] = '.'
        else:
            break
        
        # end 지점에 도달했다면 종료
        if (nr, nc) == end:
            break

        # 다음 위치
        nr += dr[d]
        nc += dc[d]

    return next_start


def func(start, count):
    global result

    # 재귀
    r, c = start
    can_go = 0
    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        # 해당 방향으로 갈 수 있으면 쭉 이동하기
        if 0 <= nr < R and 0 <= nc < C and IN[nr][nc] == '.':
            can_go = 1
            # (nr, nc) 부터 쭉 이동하면서 방문체크 => next_start: 다음 시작점
            next_start = go_or_back((nr, nc), d, 1)
            func(next_start, count + 1)
            # 재귀 나온 후 next_start 부터 (nr, nc)까지 방문 해제 (방향은 반대 방향)
            go_or_back(next_start, (d + 2) % 4, 0, (nr, nc))
    
    # 종료 조건 => 갈 수 있는 곳이 없는 상태
    if not can_go:

        # 모든 칸을 방문했는지 확인
        board_count = 0
        for i in range(R):
            for j in range(C):
                board_count += 1 if IN[i][j] == 'O' else 0

        # board 칸을 모두 방문했다면 result 갱신
        if board_count == total_board_count:
            result = min(result, count)


count = 0
while 1:
    count += 1

    try:
        R, C = map(int, input().split())
        IN = [list(input()) for _ in range(R)]

        # board 칸의 개수 구하기
        total_board_count = 0
        for r in range(R):
            for c in range(C):
                total_board_count += 1 if IN[r][c] == '.' else 0
                       
        # 함수 시작 => 모든 위치에서 함수 실행하여 확인하기
        result = 99999999999999999
        for r in range(R):
            for c in range(C):
                if IN[r][c] == '.':
                    IN[r][c] = 'O'
                    func((r, c), 0)
                    IN[r][c] = '.'
            
        # 모든 빈 칸을 방문할 수 있는 경우가 없다면 -1
        if result == 99999999999999999:
            result = -1
        print(f'Case {count}: {result}')

    except:
        break