[카카오][Python3] 리틀 프렌즈 사천성

2017년 카카오 코드 페스티벌 본선 3번 문제를 풀어보았다. 문제를 제대로 읽지 않았더니 다 풀어놓고도 계속 틀렸다는... 주어진 모든 알파벳 문자를 제거하지 못하고 1개라도 남으면 IMPOSSIBLE 이라는 점을 주의해야 한다.

참고 : http://tech.kakao.com/2017/09/14/code-festival-round-2/

입력은 위 문제와 조금 다르게 한줄씩 들어오는 기준이다.

예제 입력 :

4 4

.ZI.

M.**

MZU.

.IU.

#!/usr/bin/env python3


def find_route(m1, n1, m2, n2, c):
    up, down, left, right = check_edges(m1, n1, m2, n2, c)
    case = (m1-m2)*(n1-n2)
    if case == 0:
        return (m1 == m2 and up) or (n1 == n2 and left)
    elif case > 0:
        return (up and right) or (down and left)
    else:
        return (up and left) or (down and right)


def check_edges(m1, n1, m2, n2, c):
    up, down, left, right = [True]*4
    for i in range(min(n1, n2), max(n1, n2)+1):
        if matrix[min(m1, m2)][i] not in ('.', c):
            up = False
            break
    for i in range(min(n1, n2), max(n1, n2)+1):
        if matrix[max(m1, m2)][i] not in ('.', c):
            down = False
            break
    for i in range(min(m1, m2), max(m1, m2)+1):
        if matrix[i][min(n1, n2)] not in ('.', c):
            left = False
            break
    for i in range(min(m1, m2), max(m1, m2)+1):
        if matrix[i][max(n1, n2)] not in ('.', c):
            right = False
            break
    return up, down, left, right


m, n = map(int, input().split())
matrix = []
coordinates = {}
for i in range(m):
    row = list(input())
    matrix.append(row)
    for j in range(n):
        c = row[j]
        if c.isupper():
            coordinates.setdefault(c, []).append((i, j))

result = []
friends = sorted(coordinates)
i = 0
while i < len(friends):
    c = friends[i]
    if c in result or c == '.':
        i += 1
        continue
    (m1, n1), (m2, n2) = coordinates[c]
    if find_route(m1, n1, m2, n2, c):
        result.append(c)
        friends[i] = '.'
        matrix[m1][n1] = '.'
        matrix[m2][n2] = '.'
        i = 0
        continue
    i += 1


if len(result) == len(friends):
    print(''.join(result))
else:
    print('IMPOSSIBLE')