[Python] 코드트리 / 마법의 숲 탐색 (라이브러리 안 쓴 풀이)

문제 링크

 

문제 풀이 전략

 

문제 설명이 약간은 모호하게 되어있어서, 솔직히 실전 코딩테스트였으면 많이 당황스러웠을 것 같다.

1. 골렘 한 대 안착
2. 정령 이동
3. 그 다음 골렘 안착
4. 정령 이동
5. ...

을 반복하는 것인지,

1. 골렘 한 대 안착
2. 그 다음 골렘 안착
3. ... 그렇게 해서 모든 골렘이 안착
4. 그 이후에 정령이 이동하기 시작

을 반복하는 것인지 조금 헷갈리기는 하는데, 어느 골렘의 일부분이라도 숲 밖으로 벗어나면 숲 내 골렘이 전부 숲 밖으로 나가야 하므로 전자라고 해석하는 것이 타당하다.

 

코드트리 공식 풀이에는 BFS를 이용한다. 나도 BFS를 이용하기는 했는데, 이게 조금은 더 효율적인 풀이라고 생각한다.

 

 

이렇게 딕셔너리에 골렘의 중간 좌표와 출구 방향을 정해가면서, 동시에 딕셔너리에 추가할 때마다 탐색을 진행해야 한다.

 

 

하지만 모든 좌표를 다 탐색할 필요 없이, 그곳을 중심으로 하는 골렘이 있었더라면 건너갈 수 있을 좌표만을 탐색하면 된다. 그 좌표들이 실제로 딕셔너리에 있는지 없는지 검색할 건데, 이 검색 과정은 O(1)이므로 굉장히 효율적으로 진행할 수 있다.

 

queue에 처음에는 자기자신의 중간좌표만을 넣고 시작하는데, 탐색 중 실제로 그 좌표를 중심으로 하는 골렘이 발견된다면 그 좌표를 queue에 추가하면 된다. 이는 BFS이다. 동시에 최남단값을 관리해줘야 하는데, 이는 탐색 중에 도달 가능성이 있는 것으로 밝혀진 골렘 중, 가장 남쪽에 있는 골렘의 중간 좌표 r값에 1을 더하면 된다.

 

정답 코드

R, C, K = map(int, input().split())

spirits = list()
for _ in range(K) :
    spirits.append(list(map(int, input().split())))

world = [[0]*(C) for _ in range(R+3)] #골렘 크기 3을 감안하여 숲 지도 행을 3 늘림
directions = dict()

answer = 0
#정령이 골렘을 타고 내려옴
spirit_num = 0 
for c, d in spirits :

    spirit_r = 1
    spirit_c = c-1
    direction = d

    while True :
        down_available = (spirit_r < R+1 and 0 < spirit_c < C-1 and
                        world[spirit_r+2][spirit_c] == 0 and 
                        world[spirit_r+1][spirit_c-1] == 0 and 
                        world[spirit_r+1][spirit_c+1] == 0)

        if down_available : 
            spirit_r += 1
            continue

        left_available = (spirit_r < R+1 and 1 < spirit_c < C-1 and
                        world[spirit_r-1][spirit_c-1] == 0 and 
                        world[spirit_r+1][spirit_c-1] == 0 and 
                        world[spirit_r+2][spirit_c-1] == 0 and
                        world[spirit_r][spirit_c-2] == 0 and
                        world[spirit_r+1][spirit_c-2] == 0)

        if left_available :
            spirit_r += 1
            spirit_c -= 1
            direction -= 1
            direction %= 4
            continue

        right_available = (spirit_r < R+1 and 0 < spirit_c < C-2 and
                        world[spirit_r-1][spirit_c+1] == 0 and 
                        world[spirit_r+1][spirit_c+1] == 0 and 
                        world[spirit_r+2][spirit_c+1] == 0 and
                        world[spirit_r][spirit_c+2] == 0 and
                        world[spirit_r+1][spirit_c+2] == 0)

        if right_available :
            spirit_r += 1
            spirit_c += 1
            direction += 1
            direction %= 4
            continue
        break

    if spirit_r < 4 :
        #골렘이 숲 내 안착 실패 시 숲 초기화
        world = [[0]*(C) for _ in range(R+3)]
        directions = dict()
        continue

    world[spirit_r][spirit_c] = 1
    world[spirit_r+1][spirit_c] = 1
    world[spirit_r-1][spirit_c] = 1
    world[spirit_r][spirit_c+1] = 1
    world[spirit_r][spirit_c-1] = 1

    """
       0
       |
  3 ___|___ 1
       |
       2
    """

    directions[(spirit_r, spirit_c)] = direction
    queue = [(spirit_r, spirit_c, direction)]
    max_r = 0
    seen = set()
    seen.add((spirit_r, spirit_c))

    while queue :
        r, c, d = queue.pop(0)
        max_r = max(max_r, r+1)

        if d%4 == 0 :
            for nr, nc in [(r-3, c), (r-2, c+1), (r-2, c-1), (r-1, c-2), (r-1, c+2)] :
                if (nr, nc) in directions and (nr, nc) not in seen :
                    queue.append((nr, nc, directions[(nr, nc)]))
                    seen.add((nr, nc))

        elif d%4 == 1 :
            for nr, nc in [(r-2, c+1), (r-1, c+2), (r, c+3), (r+1, c+2), (r+2, c+1)] :
                if (nr, nc) in directions and (nr, nc) not in seen :
                    queue.append((nr, nc, directions[(nr, nc)]))
                    seen.add((nr, nc))

        elif d%4 == 2 :
            for nr, nc in [(r+3, c), (r+2, c+1), (r+2, c-1), (r+1, c-2), (r+1, c+2)] :
                if (nr, nc) in directions and (nr, nc) not in seen :
                    queue.append((nr, nc, directions[(nr, nc)]))
                    seen.add((nr, nc))

        elif d%4 == 3 :
            for nr, nc in [(r-2, c-1), (r-1, c-2), (r, c-3), (r+1, c-2), (r+2, c-1)] :
                if (nr, nc) in directions and (nr, nc) not in seen :
                    queue.append((nr, nc, directions[(nr, nc)]))
                    seen.add((nr, nc))

    answer += max_r-2

print(answer)