[12887] 경로 게임 - python 풀이

알고리즘 설계 기법

• Backtracking

이번 문제의 경우 1)경로는 반드시 존재하고 2)행의 개수는 항상 2라는 조건 덕분에 문제가 까다롭지 않았다.

[0][i] 가 '#'이면 무조건 [1][i]는 '.'일 것이기 때문에, 푸는 방법 자체는 백트레킹이었음에도 불구하고 방문 표시를 하지 않고 지나가도 괜찮다.

 

바꿔도 무방한, 즉 최단경로에 속하지 않는 '.'의 개수를 구하는 것이 문제였으므로 전체에서 (최단경로+'#'개수)를 빼면 답을 구할 수 있다. → M*2 - (거쳐간 '.'개수 + '#'개수)

 

여기서 놓치면 안되는 부분!

출발 위치는 [0][0] 과 [1][0] 두 개다. 난 이걸 놓쳐서 자꾸 애먹었다...

 

만약 입력으로

5
.#...
.....

가 들어온다면[0][0]에서 출발할 경우 → 출력 : 3[1][0]에서 출발할 경우 → 출력 : 4즉 [1][0]에서 출발하는 것이 최단경로가 되므로, 각각 경로를 탐색하고 거리를 비교하는 과정이 필요하다.

 

답

M = int(input())
Map = []
for _ in range(2):
    Map.append(list(input()))

def isBlack(_):
    if _ == '#': return True
    return False

def getLength(i,j): #시작 위치 [i][j]
    length = 1
    while j != M:
        if isBlack(Map[i][j]):
            if i == 1:
                i = 0
            else:
                i = 1
            if j != 0:
                length += 1
        else:
            j += 1
            length += 1
    return length-1 #인덱스 초과됐으므로 -1

length = min(getLength(0,0), getLength(1,0))
black = Map[0].count('#') +Map[1].count('#')
print((M*2)-(length+black))

문제 풀러가기

12887번: 경로 게임

해답을 얻은 곳: https://burningjeong.tistory.com/587