🐹 사다리 타기

1. 문제 링크

2469번: 사다리 타기

2. 코드

Python3 31256KB 84ms

k = int(input())
n = int(input())
alpha = [chr(65 + i) for i in range(k)]
start_order = list(' '.join(alpha))
final_order = list(' '.join(list(input())))
h_len = len(start_order)
ladder = []
ladder.append(start_order)
for i in range(n):
    line = list(input())
    line = list(' ' + ' '.join(line) + ' ')
    if '?' in line:
        hidden = i + 1  # 물음표 가로줄 위치
    ladder.append(line)
ladder.append(final_order)

final_idx = []
for a in final_order:
    final_idx.append(start_order.index(a))

# 같은 알파벳 물음표에서 만나서 길찾기
def connect_road(idx):
    sx, sy = 0, idx
    ex, ey = n+1, final_idx.index(idx)
    # 위에서 물음표까지 내려가기
    while sx != hidden:
        sx += 1
        # 물음표 라인 도착시 움직이지 않도록 함
        if sx == hidden:
            break
        # 왼쪽에 막대기 있을 시 왼쪽으로 이동
        if 0 < sy - 1 and ladder[sx][sy - 1] == '-':
            sy -= 2
        # 오른쪽에 막대기 있을 시 오른쪽으로 이동
        elif sy + 1 < h_len and ladder[sx][sy + 1] == '-':
            sy += 2
    # 밑에서 물음표까지 올라가기
    while ex != hidden:
        ex -= 1
        # 물음표 라인 도착시 움직이지 않도록 함
        if ex == hidden:
            break
        # 왼쪽에 막대기 있을 시 왼쪽으로 이동
        if 0 < ey - 1 and ladder[ex][ey - 1] == '-':
            ey -= 2
        # 오른쪽에 막대기 있을 시 오른쪽으로 이동
        elif ey + 1 < h_len and ladder[ex][ey + 1] == '-':
            ey += 2
    # 가로 길이 차이가 3이상 날 경우(실제로는 가로 한 칸 차이보다 클 경우)
    if abs(sy - ey) > 2:
        return False    # 사다리 불가능한 경우
    # 다리를 안놔도 만나는 경우
    if sy == ey:
        return True
    # 다리 놓기(중복으로 놓기 가능)
    ladder[hidden][max(sy, ey)-1] = '-'
    return True

fail = False

for i in range(h_len):
    if start_order[i] == ' ':
        continue
    # 불가능한 경우
    if not connect_road(i): 
        print('x' * (k-1))
        fail = True
        break

if not fail:
    print(''.join(ladder[hidden]).replace(' ', '').replace('?', '*'))

3. 해설

A   B   C   D   E   F   G   H   I   J 
  *   -   *   *   *   -   *   *   *   
  -   *   -   *   *   *   *   *   *   
  ?   ?   ?   ?   ?   ?   ?   ?   ?   
  -   *   *   -   *   *   *   -   *   
  *   *   -   *   -   *   -   *   -   
A   C   G   B   E   D   J   F   I   H

위처럼 시작점과 빈칸이 있는 사다리 모양을 만든다.

같은 알파벳의 시작 위치와 끝 위치의 인덱스를 ?의 위치로 사다리를 타면서 옮긴 후

1. 바로 만나면(인덱스가 똑같으면) 다리를 놓지 않고
2. 가로로 2칸 차이가 날 때는 그 사이에 다리를 놓고
3. 가로가 2칸보다 더 크게 차이가 날 때는 불가능한 경우임(다리가 길이 1이 넘으면 안되기 때문)

3번일 경우는 바로 x를 k 길이만큼 출력하고 2의 경우 다리를 다 놓은 후 ? 자리는 *로 변경해 출력