[백준] #16954 Python

백준 16954번 파이썬https://www.acmicpc.net/problem/16954

아이디어

라기 보다는,, 반성문 느낌

1. 그래프 자체를 주어진 문제 그대로 가지고 있는다, 벽이 이동해서 없어지면 말 그래도 pop을 해주고 새로운 벽을 index 0에 insert해준다(벽에 해당하는 #을 좌표로 반환하여 현 위치와 비교하면 엄청난 시간초과 발생 -> 처음엔 이렇게 했다,,,)
2. [수 많은 루트 중 하나만 성공해도 1을 출력하면 된다] -> queue를 활용해서 BFS로 푼다(왜인진 모르겠지만 처음엔 재귀함수를 사용해서 DFS로 풀 생각을 했다,,,)

전체코드

from sys import stdin
from collections import deque


def visitable(x, y, visited):
    return 0 <= x < 8 and 0 <= y < 8 and graph[x][y] == '.' and not visited[x][y]


def bfs(start):
    q = deque([start])
    dirs = ((0, 0),
            # 상하좌우
            (0, 1), (0, -1), (1, 0), (-1, 0),
            # 대각선
            (1, 1), (1, -1), (-1, 1), (-1, -1))

    while q:
        # 벽이 이동한 후에, 다시 체크해줘야한다.
        visited = [[False] * 8 for _ in range(8)]
        for _ in range(len(q)):
            cur_y, cur_x = q.popleft()

            if [cur_y, cur_x] == [0, 7]:
                return 1

            if graph[cur_y][cur_x] == '#': # 벽이 이동한 후 체크
                continue

            for y, x in dirs:
                next_y, next_x = cur_y + y, cur_x + x

                if visitable(next_y, next_x, visited):
                    visited[next_y][next_x] = True
                    q.append([next_y, next_x])

        # 행을 아래로 이동
        graph.pop()
        graph.insert(0, ['.', '.', '.', '.', '.', '.', '.', '.'])

    return 0


if __name__ == '__main__':
    graph = [list(stdin.readline().strip()) for _ in range(8)]
    print(bfs([7, 0]))

느낀점

• 그래프를 다룰 땐 그 자체를 graph에 저장해야 될 때도 있다.
• DFS/BFS 구별 연습하기