[백준] 2469번: 사다리 타기(Python)

문제 링크

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

2469번: 사다리 타기

 

풀이

• 처음 아이디어로는 '?'를 제외한 나머지 사다리를 탄 후 결과 값과 비교하려 했지만 -> '?'의 위치도 중요해서 복잡해짐.

[풀이 참고함]

핵심: 가로줄이 있으면 두 알파벳이 교환된다.

1. 첫 줄(초기값) ~ 물음표 줄 전까지 사다리 타기 진행 & 맨 밑(결과)~물음표 다음줄까지 진행 (아래서 위로)
2. 그럼 물음표 줄을 가운데에 두고 before, '???', after 이런 식으로 3 줄이 만들어진다.
3. 이때 before, after 의 알파벳 줄을 비교하며 '???'줄을 채우는 것이다. 
   1. '-' 가 놓이려면 알파벳이 2개가 서로 교환되어야 하므로, 두칸 이상 이동하는 경우 'xxx'를 출력하게 한다. 

 

코드

k = int(input())
n = int(input())

array2 = list(input())

# 이차배열로 만들어서 사다리를 만나면 내려가기
ladder = []
line = 0
for index in range(n):
    row = list(input())
    if row[0] == '?':
        line = index
    ladder.append(row)

# 시작 배열
array = []
for i in range(k):
    array.append(chr(i + 65))

# 위에서부터 '?' 까지 사다리 타기
for i in range(line):
    for j in range(k-1):
        if ladder[i][j] == '-':
            array[j], array[j+1] = array[j+1], array[j]

# 밑에서부터 '?' 까지 사다리 타기
for i in range(n-1, line, -1):
    for j in range(k - 1):
        if ladder[i][j] == '-':
            array2[j], array2[j + 1] = array2[j + 1], array2[j]

# 이동 수 구하는 배열
temp = [0] * k
for i in range(k):
    for j in range(k):
        if array[i] == array2[j]:
            temp[i] = j-i

result = ''
for i in range(k):
    if abs(temp[i]) >= 2:
        result = 'x' * (k-1)
if not result:
    for i in range(k-1):
        if temp[i] != 0 and temp[i] + temp[i+1] == 0:
            result += '-'
            temp[i], temp[i+1] = 0, 0
        else:
            result += '*'

    if len(result) < k-1:
        result = 'x' * (k-1)

print(result)