백준 128871 [12887] 경로 게임 - python 풀이 알고리즘 설계 기법 Backtracking 이번 문제의 경우 1)경로는 반드시 존재하고 2)행의 개수는 항상 2라는 조건 덕분에 문제가 까다롭지 않았다. [0][i] 가 '#'이면 무조건 [1][i]는 '.'일 것이기 때문에, 푸는 방법 자체는 백트레킹이었음에도 불구하고 방문 표시를 하지 않고 지나가도 괜찮다. 바꿔도 무방한, 즉 최단경로에 속하지 않는 '.'의 개수를 구하는 것이 문제였으므로 전체에서 (최단경로+'#'개수)를 빼면 답을 구할 수 있다. → M*2 - (거쳐간 '.'개수 + '#'개수) 여기서 놓치면 안되는 부분! 출발 위치는 [0][0] 과 [1][0] 두 개다. 난 이걸 놓쳐서 자꾸 애먹었다... 만약 입력으로 5 .#... ..... 가 들어온다면[0][0]에서 출발할 경우 → 출력.. 2022. 3. 19. 이전 1 다음