알고리즘 설계 기법
- 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))
문제 풀러가기
해답을 얻은 곳: https://burningjeong.tistory.com/587
'백준' 카테고리의 다른 글
[미해결][12976] 돌 옮기기 - python 코드 (0) | 2022.03.23 |
---|---|
[3029] 경고 - python 풀이 (0) | 2022.03.22 |
[3028] 창영마을 - python 풀이 (0) | 2022.03.22 |
[14501] 퇴사 - python 풀이 (0) | 2022.03.18 |
[9661] 돌 게임 7 - python 풀이 (0) | 2022.03.17 |
댓글