[백준] 2240 자두나무 (골드 5)

queue를 사용하여 bfs 느낌으로 풀이를 시도했습니다.

 

자두의 위치, 움직인 횟수, 지나간 초 를 상태를 구성하는 요소들로 생각하고, 배열의 값은 그 상태에서 가질 수 있는 최대 자두개수를 저장하였다. --> 이 아이디어가 문제 푸는 핵심 아이디어입니다.

 

예를 들어 1번나무, 3번 움직임, 6초 지남 상황에서 지금까지 탐색한 최대 자두개수가 3이라고 할게요.

큐의 원소를 꺼내서 다음 상황을 보았는데 1번나무, 3번 움직임, 6초 지남이 등장하였고, 자두개수는 5가 된다고 하면 배열을 업데이트해주었습니다.

 

배열 업데이트와 동시에 큐에 삽입하고, answer에 현재 얻은 자두가 최대일 지 모르니 매번 더 큰값을 할당해주었습니다.

 

한가지 트릭은 비트 연산자를 사용하여 현재 자두의 위치와 자두가 떨어지는 위치를 파악해 잡을 수 있는 지 없는 지를 한 문장으로 얻을 수 있었습니다.

 

from collections import deque
import sys
input = sys.stdin.readline

T, W = map(int, input().rstrip().split())

queue = deque()

## visitded[위치][움직인횟수][초] = 자두 개수 ==> 더 크면 큐에 삽입하는 방식
## 위치 : 0 또는 1
## 움직인 횟수 : 0 <=  <= 30
## 초 : 0 <= <= 1000
## --> 약 60000개 정도 저장하는 배열

visited = [[[-1 for _ in range(1001)] for _ in range(1001)] for _ in range(2)]
queue.append((0,0,0))
visited[0][0][0] = 0

answer = 0
for _ in range(T):
    jaduFall = int(input().rstrip())

    jaduFall -= 1

    nowQueueLen = len(queue)

    
    for _ in range(nowQueueLen):
    
        loc, move, second = queue.popleft()

		## 현재 상태에서 가질 수 있는 최대 자두 개수
        curCount = visited[loc][move][second]

                
        ## 그 자리에 계속 머무는 경우
        jaduGet = loc^jaduFall^1 ## 자두와 같은 자리면 자두개수+1, 아니면 자두개수 그대로 
        if visited[loc][move][second+1] < curCount + jaduGet:
            visited[loc][move][second+1] = curCount + jaduGet
            queue.append((loc,move,second+1))
            answer = max(answer , curCount + jaduGet) ## 자두 최대값 저장

        ## 자리를 옮기는 경우
        loc = loc^1 ## 자리 옮기기
        jaduGet = loc^jaduFall^1 ## ## 옮긴 자두와 같은 자리면 자두개수+1, 아니면 자두개수 그대로 
        if visited[loc][move+1][second+1] < curCount + jaduGet and move < W:
            visited[loc][move+1][second+1] = curCount + jaduGet
            queue.append((loc,move+1,second+1))
            answer = max(answer , curCount + jaduGet) ## 자두 최대값 저장


print(answer)