[시뮬레이션] (코드트리) 마법의 숲 탐색 - 파이썬

✅ 링크: https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration?&utm_source=clipboard&utm_medium=text

✅ 일단 이문제 올해 상반기에 삼전에서 못 풀었는데 지금 풀 수 있었다는 것에 감격했다. 성장을 하고 있구나..고통 속에 살고 있었는데 칭찬한다 내 자신..!

✅ 처음에 시간 잡아먹었던 부분 원인: 서/동쪽 이동하고 + 아래까지 내려가야 한 번 이동을 마친거다. (서/동쪽 이동만 해서 시간 날림)

문제를 잘 읽자!

✅ flag 써서 이동 없으면 break문 돌도록 해야한다.  뭔가 이상한 이전 좌표를 잘못 기록해서 시간 날림
✅ visited로 중복을 굳이 안막아도 되었다. (왜냐면 어차피 내려가니까 다시 올라가는 경우는 없어서)

1) 내려간다. 초록색 3좌표 비어있어야함

2) 왼쪽 이동후 아래 이동. 초록색 5좌표 비어있어야함

3) 오른쪽 이동 후 아래이동. 초록색 5좌표 비어있어야함

관련 코드:

for i,(c,d) in enumerate(golem_list):
    r,c = 0,c-1 #1번째열 -> 0번째열
    br,bc = 0,0
    flag = False
    while True:
        if (check_direction(r+1,c,[0,1,0],[1,0,-1]):
            flag=True
            r,c = r+1,c 
        elif check_direction(r,c-1,[-1,1,0,1,2],[0,0,-1,-1,0]):
            flag=True
            r,c = r+1,c-1
            d = 3 if d-1<0 else d-1
        elif check_direction(r,c+1,[-1,0,1,2,1],[0,1,0,0,1]):
            flag=True
            r,c = r+1,c+1
            d = (d+1)%4
        if not flag :
            break
        flag = False

 

✅ d 라는 변수가 이곳 저곳에 쓰여서 최종 좌표가 잘못 저장되는 경우가 있었다.
가급적 r,c,d 이런거와 지속해서 쓸 변수 이름을 초기부터 분리해놓자.

✅ 그래프 상단 부분을 늘리는 것과 골렘을 구분하는 센스를 좀 늦게 생각했다.

✅ 범위도 그래프 상단을 늘린거니까 r<4인데 r<=4로 해버려서 시간 잡아 먹었다. 무조건 범위 다시 보자.
✅ 마지막에 q에 넣을때도 리스트[0]으로 해서 튜플만 넣어줘야하는데 그거때매 또 시간 잡아 먹었다. 리스트에서 뺄때 유의하자

✅ 전체 코드

from collections import deque
R,C,K = map(int,input().split())
golem_list = [list(map(int,input().split())) for _ in range(K)]
answer = 0
R += 3
forest = [[0]*C for _ in range(R)]
forest_q = [[] for _ in range(K+1)]
dr = [-1,0,1,0]
dc = [0,1,0,-1]
def check_range(r,c):
    return 0<=r<R and 0<=c<C


def check_direction(r,c,dr,dc):
    for ddr,ddc in zip(dr,dc):
        nr,nc = r+ddr,c+ddc
        if not(check_range(nr,nc)):
            return False
        if forest[nr][nc] != 0:
            return False
    return True

for i,(c,d) in enumerate(golem_list):
    r,c = 0,c-1
    br,bc = 0,0
    flag = False
    while True:
        if (check_direction(r+1,c,[0,1,0],[1,0,-1])):
            flag=True
            r,c = r+1,c 
        elif check_direction(r,c-1,[-1,1,0,1,2],[0,0,-1,-1,0]):
            flag=True
            r,c = r+1,c-1
            d = 3 if d-1<0 else d-1
        elif check_direction(r,c+1,[-1,0,1,2,1],[0,1,0,0,1]):
            flag=True
            r,c = r+1,c+1
            d = (d+1)%4
        if not flag :
            break
        flag = False

    if r<4:
        forest =[[0]*C for _ in range(R)]
        continue
    else:
        forest[r][c]=i+1
        for direct in range(4):
            nr,nc = r+dr[direct],c+dc[direct]
            forest[nr][nc]=i+1

    forest_q[i+1].append((r,c,d))
    q = deque()
    q.append((r,c,d))
    visited = [(r,c,d)]
    result = 0
    while q:
        now = q.popleft()
        exit = (now[0]+dr[now[2]],now[1]+dc[now[2]])
        result = max(now[0]+1-2,result)
        for direct in range(4):
            nr,nc = exit[0]+dr[direct],exit[1]+dc[direct]
            if not(check_range(nr,nc)):
                continue
            if forest[nr][nc]!=0 and forest[nr][nc]!=i+1 and forest_q[forest[nr][nc]] not in visited:
                q.append(forest_q[forest[nr][nc]][0])
                visited.append(forest_q[forest[nr][nc]])
    answer+=result
print(answer)