[solved.ac 골드3] 9944_NxM 보드 완주하기 (파이썬, 백트래킹)

 

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

 

문제

N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다.

게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다.

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

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

아래 그림은 총 10단계 만에 모든 칸을 방문하는 방법이다.

보드의 상태가 주어졌을 때, 모든 칸을 방문하기 위한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 보드의 크기를 나타내는 N과 M이 주어진다. N은 세로 크기, M은 가로 크기이고, 두 값은 30보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다. 보드의 상태는 장애물을 나타내는 '*'과 빈 칸을 나타내는 '.'으로 이루어져 있다.

입력으로 주어진 보드가 장애물로만 이루어진 경우는 없다.

출력

각 테스트 케이스마다 보드의 모든 빈 칸을 방문하는 최소 이동 횟수를 출력한다. 출력 형식은 예제를 참고한다.

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

예제

---

나의 풀이

언뜻 생각해봐도 시간 복잡도가 높을 것 같은 문제이다. 다행히 시간은 넉넉히 주고 있다.

 

기본적인 아이디어는

1. 일단 이동 해본다
2. 더 갈 수 있으면 간다
3. 더 이상 갈 수 없으면 모든 칸을 탐색했는지 확인한다
   1. 모든 칸을 탐색한 경우 최소 이동 횟수를 갱신한다
   2. 모든 칸을 탐색하지 못한 경우 가장 최근에 탐색한 경로를 되돌아간다(취소한다)
4. 1~3 과정을 출발할 수 있는 모든 위치에서 탐색해본다.

 

탐색해보고 되돌아가고 하는 과정은 백트래킹 기법을 통해서 할 수 있다.

보통 visited 리스트를 두고 한 번 방문한 위치는 다시 방문하지 않도록 설정하는 과정이 있는데 이번 풀이에서는 한 번 지나간 위치는 '*'(장애물) 로 설정해 다시 방문하지 못하도록 했다.

 

전체 코드

INF = 10 ** 9
case = 1


def check():
    return board == [['*'] * M for _ in range(N)]


def rec_fun(x, y, count):
    global answer
    if check(): # 모든 위치 방문 성공
        answer = min(answer, count) # 최소 이동 횟수 갱신
    if answer < count: return # answer 를 넘기면 더 이상 진행 의미 없음

    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: # 상, 하, 좌, 우 탐색
        passed = list() # 지나온 위치를 저장할 리스트
        nx, ny = x, y
        while True: # 한 방향으로 쭉 이동
            nx += dx
            ny += dy
            if nx in range(N) and ny in range(M) and board[nx][ny] == '.':
                passed.append((nx, ny)) # 지나온 위치 저장
                board[nx][ny] = '*' # 지나온 위치 장애물로 변경
            else:
                break
        if passed: # 지나온 위치가 있는 경우
            rec_fun(nx - dx, ny - dy, count + 1) # 다음 탐색

        for px, py in passed: # 지나온 위치 원위치
            board[px][py] = '.'


while True:
    try:
        N, M = map(int, input().split())
        board = [list(input()) for _ in range(N)]
        answer = INF
        for i in range(N):
            for j in range(M):
                if board[i][j] == '.':
                    board[i][j] = '*' # 시작 위치 장애물로 설정
                    rec_fun(i, j, 0) # 탐색 시작
                    board[i][j] = '.' # 시작 위치 원상 복구
        if answer == INF: # 모든 위치를 탐색한 경우가 한 번도 없음
            answer = -1
        print(f'Case {case}: {answer}')
        case += 1
    except:
        break

 

채점 결과 (Python 3)

채점 결과 (PyPy3)