뭐였더라

불이 퍼진 곳은 지훈이가 갈 수 없다. BFS로 먼저 불이 번지는 시간을 기록해두고, 불이 아에 번지지 않았거나 불이 아직 퍼지기 전이라면 지훈이를 이동시킨다.

from collections import deque

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

# 불 이동
def bfs_fire():
    q_F = deque(F)
    while q_F:
        x, y = q_F.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
			
            # 불이 퍼진 시각 기록
            if (0 <= nx < C and 0 <= ny < R
                and (visited_F[ny][nx] == -1
                     or visited_F[ny][nx] > visited_F[y][x]+1)
                and maze[ny][nx] != '#'):

                q_F.append([nx, ny])
                visited_F[ny][nx] = visited_F[y][x] + 1

# 지훈 이동
def bfs_jihoon():
    q_J = deque([J])

    while q_J:
        x, y = q_J.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 지훈이가 방문하는 시각 기록
            if (0 <= nx < C and 0 <= ny < R
                and visited_J[ny][nx] == -1
                and maze[ny][nx] == '.'
                and (visited_F[ny][nx] > visited_J[y][x]+1 # 불보다 먼저 도달했거나
                     or visited_F[ny][nx] == -1)):         # 불이 닿지 않은 영역
                visited_J[ny][nx] = visited_J[y][x] + 1
                q_J.append([nx, ny])

                # 가장자리에 도달했다면 탈출
                if (nx == 0 
                    or ny == 0 
                    or nx == C-1 
                    or ny == R-1):
                    return visited_J[ny][nx] + 1
                
    return 'IMPOSSIBLE'


R, C = map(int, input().split())
maze = [list(input()) for _ in range(R)]


J = [0, 0]
F = []
for i in range(R):
    for j in range(C):
        if maze[i][j] == 'J':
            J = [j, i]
        if maze[i][j] == 'F':
            F.append([j, i])

visited_J = [[-1 for _ in range(C)] for _ in range(R)]
visited_F = [[-1 for _ in range(C)] for _ in range(R)]

# 지훈이랑 불 시작 위치 기록
visited_J[J[1]][J[0]] = 0
for f_x, f_y in F:
    visited_F[f_y][f_x] = 0

# 처음부터 가장자리라면 바로 탈출
if (J[0] == 0 or J[0] == C-1
    or J[1] == 0 or J[1] == R-1):
    print(1)
else:
    bfs_fire()
    print(bfs_jihoon())

예시처럼 일정표가 있을 때 수익은

• 7일에는 일을 하지 못한다.
• 6일에도 일을 하지 못한다.
• 5일에 시작해서 6일에 끝낸다(15). 7일에 일을 할 수 있다면 한다.
• 4일에 일을 끝낸다(20). 5일 이후에 가능한 일을 한다(15). -> 35
• 3일에 일을 끝낸다(10). 4일 이후에 가능한 일을 한다(35). -> 45
• 2일에 시작해서 6일에 끝낸다(20). 7일에 일을 할 수 있다면 한다.
• 1일에 시작해서 3일에 끝낸다(10). 4일 이후에 가능한 일을 한다(35). -> 45

로 마지막 날부터 계산할 수 있다. i일차의 수익을 dp[i]에 저장할 때 아래와 같이 작성하면 된다.

N = int(input())
schedules = [list(map(int, input().split())) for _ in range(N)]

dp = [0 for _ in range(N+1)]
for i in range(N-1, -1, -1):
	# 현재 날짜와 일하는데 걸리는 날이 전체 날짜보다 크다면
    if i + schedules[i][0] > N:
        dp[i] = dp[i+1] # 오늘은 일 못한다. 내일 수익으로 저장
        continue

	# 내일 수익과, 오늘 수익에 오늘 일정이 끝난 날 이후의 수익을 더한 값을 비교해
    # 오늘까지의 수익으로 저장한다.
    dp[i] = max(dp[i+1], schedules[i][1] + dp[i+schedules[i][0]])

print(dp[0])

큐를 이용한 구현 문제다. 큐에 뱀의 다음 머리 위치를 저장하고 꼬리 부분을 pop 시키면서 반복문을 돌아준다. 

from collections import deque

# rotation 행렬
L_rotate = [[0, 1], 
            [-1, 0]]
R_rotate = [[0, -1],
            [1, 0]]


N = int(input())
K = int(input())
apples = [list(map(int, input().split())) for _ in range(K)]
L = int(input())
turns = [list(input().split()) for _ in range(L)]

# 전체 보드
board = [[0 for _ in range(N)]
         for _ in range(N)]
# 시작 위치는 가장 왼쪽 상단이다. 뱀을 2로 둔다.
board[0][0] = 2

# 사과는 1로 둔다.
for i, j in apples:
    board[i-1][j-1] = 1

q = deque([[0, 0]]) # 시작 위치와 회전하는 시간을 큐로 저장한다.
turn = deque(turns)
move = [1, 0] # 시작 방향은 오른쪽이다.
t = 0

while q:
	# 뱀 머리 위치는 큐 가장 끝에 있다.
    x, y = q[-1]
    nx = x + move[0] # 다음 방향 설정
    ny = y + move[1] 
    t += 1

    if (0 <= nx < N and 0 <= ny < N): # 보드 내부에서만 이동
        if board[ny][nx] == 2: # 다음 위치가 뱀의 몸과 충돌한다면 종료
            break
        else:
            if board[ny][nx] == 0: # 빈 공간이라면
                x, y = q.popleft() # 꼬리 위치 pop
                board[y][x] = 0 # 꼬리 위치 빈 공간으로
            q.append([nx, ny]) # 큐에 다음 머리 위치 추가
            board[ny][nx] = 2 # 머리 이동
    else: # 보드 밖으로 나간다면 종료
        break

    if turn: # 아직 회전할게 남았다면
        time, direction = turn.popleft() # 시간과 방향 pop
        if t == int(time): 회전할 시간이라면
            if direction == 'L': # 방향에 맞게 회전
                x_move = L_rotate[0][0] * move[0] + L_rotate[0][1] * move[1]
                y_move = L_rotate[1][0] * move[0] + L_rotate[1][1] * move[1]
            else:   
                x_move = R_rotate[0][0] * move[0] + R_rotate[0][1] * move[1]
                y_move = R_rotate[1][0] * move[0] + R_rotate[1][1] * move[1]
            move = [x_move, y_move]
        else: # 아니라면 다시 큐에 저장
            turn.appendleft([time, direction])

print(t)

N = int(input())
states = list(map(int, input().split()))
S = int(input())
students = [list(map(int, input().split())) for _ in range(S)]

for g, idx in students:
    if g == 1:
        for i in range(idx-1, N, idx):
            states[i] = (1<<states[i]) & 1 # 0이면 1로, 1이면 0으로 바꾼다
    elif g == 2:
        idx -= 1 # 문제에서 번호는 1부터 시작하므로 -1 해준다.
        states[idx] = (1<<states[idx]) & 1 # 현재 위치 on/off
        for i in range(1, N):
            if (idx-i >= 0 and idx+i < N # 현재 위치 중심으로 전체 범위보다 작을 때
                and states[idx-i] == states[idx+i]): # 양 옆이 같다면
                states[idx-i] = states[idx+i] = (1<<states[idx-i]) & 1 # on/off
            else: # 범위를 벗어나거나 서로 다를 경우 종료
                break

for i in range(5): # 최대 100개의 스위치가 20개씩 출력되므로
    try:
        if states[i*20] is not None: # 첫 번째 값이 있는 리스트만 출력
            try:
                print(*states[i*20 : (i+1)*20]) # 20개가 다 있다면 20개 출력
            except:
                print(*states[i*20:]) # 아니라면 전체 출력
        else:
            break
    except:
        pass