[백준 2469번] 사다리 타기 문제 풀이 (with python)

 

 

< 문제  >

 

 

 

 

< 입출력 >

 

 

 

 

< 풀이 >

먼저, 이 문제에 감을 잡기위해 입출력을 이용해 사다리 타기가 완성되어 있다고 가정하고, 사람들이 원하는 순서대로와 동일하게 출력되는지를 테스트 해보았다. arr[ row ][ j ] 에 ' - ' 표시가 있을 경우 people[ j ]와 people[ j + 1]의 값을 교환했다.

 

import sys

input = sys.stdin.readline
n = int(input())
row = int(input())
arr = []

goal = list(input().rstrip())
people = sorted(goal)

for i in range(row):
    arr.append(list(input().rstrip()))

for i in range(row):
    for j in range(n-1):
        if arr[i][j] == '-':
            tmp = people[j]
            people[j] = people[j+1]
            people[j+1] = tmp

print(people)

원하는 순서대로와 동일한 결과임을 확인한 후, 이제 ' ? '로 알지 못할 때를 생각해 보았다.

원하는 순서의 배열과 ?표가 없이 해당 그래프를 진행했을 때 순서가 동일하지 않은 위치에 ' - ' 가  있다고 생각하여 풀려 하였는데 ' - '가 없어도 순서가 동일하지 않은 결과가 나오는 경우가 있었다.

따라서, ?가 나오기 전과 나온 후의 배열을 직접 비교해주어야 했다.

 

 

 

< 코드 >

import sys

input = sys.stdin.readline
n = int(input())
row = int(input())
arr = []

goal = list(input().rstrip())
people = sorted(goal)

left = 0            # left는 ?가 나오기 전까지의 사다리 배열
right = []          # right는 ?가 나온 후의 사다리 배열

for i in range(row):
    ladder = list(input().rstrip())
    if ladder == ['?' for _ in range(n - 1)]:        # left와 right에 각각 ?를 기준으로 전후 입력
        left = right
        right = []
        continue
    right.append(ladder)


while left:
    ladder = left.pop(0)
    for i in range(n-1):
        if ladder[i] == '-':
            people[i], people[i + 1] = people[i + 1], people[i]


while right:
    ladder = right.pop()
    for j in range(n-1):
        if ladder[j] == '-':
            goal[j], goal[j + 1] = goal[j + 1], goal[j]

ans = ['*' for _ in range(n-1)]
for k in range(n-1):
    if people[k] == goal[k + 1] and people[k + 1] == goal[k]:
        ans[k] = '-'
        people[k], people[k + 1] = people[k + 1], people[k]

if people != goal:
    ans = ['x' for _ in range(n-1)]
print(''.join(ans))