백준_3055_탈출 (python)

● 접근 방법

 문제에서 상하좌우로 이동한다는 힌트를 줘서 bfs인 것을 알았고 격자의 크기가 50으로 크지 않았기 때문에 bfs로 풀기로 결정했다.

 

● 풀이법

 문제에서 '다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.' 이런 말을 한다. 이 말을 보고 물을 먼저 움직여야겠다고 생각했다. 왜냐하면 물과 고슴도치는 동시에 움직이는 것이지만 물을 먼저 움직여놓고 도치가 움직인다고 했을 때 그 칸에 물이 있으면 즉, 물이 이동할 예정인 칸이었으면 도치가 해당 칸으로는 이동하지 못하기 때문이다. 그러나 유의해야 할 점은 필자는 여기서 많이 헤맸는데 임의로 물을 먼저 움직인다고 가정했을 뿐이지 도치와 물은 동시에 움직이는 것이다. 즉, 물을 먼저 움직여 도치가 있는 칸에 물이 들어왔다고 하더라도 사실은 동시에 움직이는 것이었기 때문에 그 고슴도치는 어딘가로 이동했을 것이다.  그 다음 bfs 문제를 풀 때 원래 입력받은 data의 보존을 위해서 visited로 방문 처리를 하는 편인데 여기서 visited를 쓰면 시간초과가 나게 된다. 격자의 크기가 그렇게 크지 않은데 visited를 쓰면 왜 시간초과가 나는지는 아직까지 잘 모르겠다. 

 

● 코드

n = int(input())
r,c = 101, 101
graph = [[0] * c for i in range(r)]
# 왼쪽 아래 오른쪽 위로
dy = [0,1,0,-1]
dx = [-1,0,1,0]
# 1세대의 시작은 오른쪽으로 가는 화살표이니
def check(x, y, d, g):
    before = [2]
    for i in range(g):
        tp = []
        tp += before
        for j in range(len(before)-1, -1, -1):
            tp.append((before[j] + 1) % 4)
        before = tp[:]
    tp = []
    for i in before:
        tp.append((i + d) % 4)
    graph[y][x] = 1
    for i in tp:
        nx = x + dx[i]
        ny = y + dy[i]
        graph[ny][nx] = 1
        x,y = nx, ny

for i in range(n):
    x,y,d,g = map(int,input().split())
    check(x, y, d, g)

answer = 0

for i in range(r-1):
    for j in range(c-1):
        if graph[i][j] == 1 and graph[i+1][j] == 1 and graph[i][j+1] == 1 and graph[i+1][j+1] == 1:
            answer += 1

print(answer)

● 회고

 문제에서 주어지지 않는 내가 정한 가정에 스스로 갇히지 말자!!