거울 설치

• 그래프를 잘 만들어서 최단거리 문제로 풀수 있는 문제
• 각 셀의 위치와 이동 방향의 조합을 노드로 모델링 할수 있다. 현재 방향으로 위치가 인접한 노드들간에는 비용이 0인 엣지를, 현재 셀이 '!' 일때 방향이 90도 차이나는 노드와는 비용이 1인 엣지를 만들어서 그래프를 만들면, 0-1 BFS와 같은 방식으로 해결할수 있다. 그냥 위치가 같은 열이나 행에 있고 방향이 같은 노드들 (=비용이 0인 엣지로 이어진 노드들)을 하나로 묶어서 노드를 만들면 일반 BFS를 돌려서 풀수도 있다. 노드의 갯수는 O(4*N^2) = O(N^2) 개이고, 각 노드는 현재 방향으로 인접한 셀로 이동하든가, 90/-90도 회전하든가 하는 3가지의 엣지가 있으므로 엣지의 갯수도 O(N^2). 총 시간복잡도는 O(N^2)
• 다른 방법은, 각 '!'와 '#'만을 노드로 갖는 그래프를 만드는 것이다. 그리고 같은 열이나 행에 해당하는 노드들끼리만 엣지로 연결해준 다음 BFS를 돌리는 것이다. 이 방법은 180도로 회전하는 것과 같은 문제 조건에 위배되는 경로도 포함해서 최단경로를 찾게 되지만, 어차피 그런 경로는 최단 경로로 선택될수 없으니까 별 문제 없다. 이 방법으로 찾아진 값은 꺾은 횟수가 아니라, 경로내의 가로방향이나 세로방향 선분의 갯수이므로, 꺾은 횟수, 즉 거울의 갯수는 이 최단거리에서 1을 뺀 값이 된다. 일반적으로는 '!'의 갯수가 적을 것이라서 이 방법이 빠를것 같긴 한데, 최악의 경우 - 모든 셀이 '!'인 경우는 N*N개의 노드가 있고, 각 노드는 O(N)개의 노드와 연결되므로, O(N^3)개의 엣지를 갖게 된다. 시간복잡도는 O(N^3).

"""Solution code for "BOJ 2151. 거울 설치".

- Problem link: https://www.acmicpc.net/problem/2151
- Solution link: http://www.teferi.net/ps/problems/boj/2151

Tags: [BFS]
"""

from teflib import tgraph

MIRROR, DOOR, WALL, EMPTY = '!', '#', '*', '.'


def main():
    N = int(input())
    grid = [input() for _ in range(N)]

    graph = []
    doors = []
    nodes_in_cols = [[] for _ in range(N)]
    for row in grid:
        nodes_in_row = []
        for nodes_in_col, cell in zip(nodes_in_cols, row):
            if cell == WALL:
                nodes_in_row.clear()
                nodes_in_col.clear()
            elif cell in (MIRROR, DOOR):
                node_num = len(graph)
                neighbors = nodes_in_row + nodes_in_col
                graph.append(neighbors)
                for neighbor in neighbors:
                    graph[neighbor].append(node_num)
                if cell == DOOR:
                    doors.append(node_num)
                nodes_in_row.append(node_num)
                nodes_in_col.append(node_num)

    answer = tgraph.min_distances(graph, doors[0])[doors[1]] - 1

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.min_distances