(Python/파이썬) - 백준(BOJ) 9944번 : NxM 보드 완주하기

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

9944번: NxM 보드 완주하기

---

• 문제 : 

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

 

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

 

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

 

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

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

 

 

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

 

 

 

---

• 풀이 :

백트래킹 문제입니다. 

 

우선 까다로웠던 점이 테스트 케이스가 몇 개인지 명시하지 않고 EOF일때까지 진행해야 한다는 점입니다.

이 부분은 아래 구문을 통해 처리해주었습니다. 

 

while True:
    try:
        N, M = map(int,input().split())
    except:
        break

 

알고리즘의 흐름입니다.

 

1. 처음 공을 놓을 위치가 지정되지 않았으므로 2중 for문으로 모든 위치를 탐색하며 공을 놓을 수 있는 자리이면 백트래킹 호출

 

2. visited 배열을 따로 생성하지 않고 탐색을 마친 위치는 board를 *로 하여 체크해줌 (탐색한 경로를 벽으로 취급)

 

3. 탐색마다 check() 함수를 호출하여 board의 모든 좌표를 탐색하였는지 확인. 이 값이 True라면 answer를 cnt와 비교하여 최솟값으로 갱신함.

 

4. 프루닝 포인트는 현재까지 경로의 탐색횟수가 answer보다 작을 경우만 다음 경로 탐색 실행 (cnt가 answer이상인 경우 다음 탐색은 무조건 최솟값이 될 수 없음.)

 

5. tmp배열을 사용하여 이번 탐색에서 지나온 좌표들을 저장. tmp 배열은 이번 탐색을 종료한 후 지나온 좌표를 "."로 초기화해주기 위함. 이 과정이 없다면 매 호출마다 NxM의 2차원 배열을 deepcopy해주어야 하며 메모리초과 발생

 

6. 상, 하, 좌, 우 4방향에 대해 while문으로 방향마다 갈 수 있는 끝까지 탐색하며 tmp에 좌표 저장.

 

7. tmp가 비어있지 않다면 해당 방향으로 탐색을 진행한 것이므로 다음 경로도 탐색해보어야 함. 따라서 bt 재귀호출

 

8. 호출 이후 tmp에 담겨있는 좌표들과 해당 탐색의 시작 좌표를 다시 "."로 초기화해줌

 

9. answer가 inf라면 모든 공간을 탐색하는 경로가 없는 것이므로 -1 출력, 아니라면 양식에 맞게 answer 출력

 

 

---

• 소스코드 : 

import sys
sys.setrecursionlimit(10**7)
answer = float('inf') # 최소 횟수를 찾기 위해 초깃값을 inf로 지정
case = 1  # 테스트케이스

# 상,우,하,좌 순서로 탐색
d = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1]
]

# board를 탐색하며 모든 좌표를 구슬이 지나갔는지 확인
# 탐색하면 *로 변경했으므로 "." 가 있으면 False 반환
def check():
    for i in range(N):
        for j in range(M):
            if board[i][j] == ".":
                return False
    return True

# 백트래킹.
# 프루닝 조건은 현재 answer보다 탐색중인 횟수 cnt가 작을 경우만 다음 번 경로 탐색
# 2차원 배열인 board를 deepcopy하여 매개변수로 전달하지 않기 위해 이번 탐색에서 지나간 좌표들을 저장하고 탐색이 끝난 후 다시 "."로 초기화해주는 방법을 사용
def bt(x, y, cnt):
    global answer
    if check(): # 모든 좌표를 탐색한 경우
        answer = min(answer, cnt) # answer를 최솟값으로 갱신
    if cnt < answer: # 현재까지 탐색한 경로의 수가 answer보다 작을 경우만 탐색
        for i in range(4): # 4방향 탐색
            tmp = [] # 지나온 좌표를 담을 배열
            ax = x
            ay = y
            while True:
                ax += d[i][0]
                ay += d[i][1]
                if 0 <= ax < N and 0 <= ay < M and board[ax][ay] == ".": # 구슬을 놓을 수 있는 공간이라면 다음 좌표 탐색
                    tmp.append([ax, ay])
                    board[ax][ay] = "*"
                else: # 구슬을 놓을 수 없다면 탐색 종료
                    break
            if tmp: bt(ax-d[i][0], ay-d[i][1], cnt + 1) # tmp가 비어있지 않다는 것은 탐색을 진행했다는 것이므로 다음 경로의 탐색도 진행하여야 함.
            for a,b in tmp: # 현재까지 지나온 좌표를 다시 "." 로 초기화
                board[a][b] = "."
        board[x][y] = "." # 시작좌표를 "."로 초기화


while True:
    try :
        N, M = map(int,input().split())
        visited = [[False for _ in range(M)] for _ in range(N)]
        board = [list(input().strip()) for _ in range(N)]
        answer = float("inf")
        for i in range(N):
            for j in range(N):
                if board[i][j] == ".": # 구슬을 놓을 수 있다면 해당 좌표에 구슬을 놓고 탐색 시작
                    board[i][j] = "*"
                    bt(i, j, 0)
        if answer == float("inf"): # 경로가 존재하지 않는 경우
            answer = -1
        print("Case {}: {}".format(case,answer))
        case += 1
    except :
        break