day15

Day 15: 산소 시스템 (Oxygen System)

https://adventofcode.com/2019/day/15

Part 1

깊은 우주에서는 많은 일들이 잘못될 수 있습니다. 다행히도 그러한 것들 중 대다수는 표시등으로 문제를 파악할 수 있습니다. 그러나 불행히도 그 표시등들 중 하나가 지금 켜져 있습니다. 우주선 일부의 산소 시스템이 고장났습니다!

판독 결과에 따르면, 산소 시스템은 산소 탱크 2가 파열되기 며칠 전에 고장났음에 틀림없습니다. 산소 수준이 위험할 정도로 낮아져서 우주선의 해당 부분이 자동으로 되었기에, 원격으로 작동되는 수리 로봇 한 대가 산소 시스템을 수리할 수 있는 유일한 선택지입니다.

엘프의 케어 패키지에는 수리 로봇을 원격으로 제어하는 데 사용할 수 있는 Intcode 프로그램(퍼즐 입력)이 포함되어 있습니다. 해당 프로그램을 실행하여 수리 로봇을 산소 시스템으로 안내하고 문제를 해결할 수 있습니다.

원격 제어 프로그램은 다음 단계를 반복해서 실행합니다:

• 입력 명령어를 통해 이동 명령을 받습니다.
• 수리 로봇에게 이동 명령을 보냅니다.
• 수리 로봇이 이동 작업을 마칠 때까지 기다립니다.
• 출력 명령을 통해 수리 로봇의 상태를 보고합니다.

수리 로봇은 다음 네 가지 이동 명령만 수행할 수 있습니다. 북쪽(1), 남쪽(2), 서쪽(3), 동쪽(4). 다른 명령은 유효하지 않습니다. 각 명령은 움직이는 방향만 다르고, 움직이는 거리는 같습니다. 충분히 긴 동서 복도에서 4,4,4,4,3,3,3,3과 같은 일련의 명령은 수리 로봇을 원래 위치로 되돌려 놓습니다.

수리 로봇은 다음 상태 코드들 중 하나로 응답할 수 있습니다:

• 0: 수리 로봇이 벽에 부딪쳤습니다. 위치는 변경되지 않았습니다.
• 1: 수리 로봇이 요청한 방향으로 한 단계 이동했습니다.
• 2: 수리 로봇이 요청한 방향으로 한 단계 이동했습니다; 새로운 위치는 산소 시스템의 위치입니다.

수리 로봇의 주변 지역에 대해 아는 바가 없으나 상태 코드를 보면 알아낼 수 있습니다.

예를 들어, 로봇은 D, 벽은 #, 로봇이 통과할 수 있는 위치는 ., 탐색되지 않은 위치는 빈 공간으로 영역을 그려보겠습니다. 그러면 초기 상태는 다음과 같습니다:

      
      
   D  
      
      

로봇을 북쪽으로 이동시키려면, 1을 보내면 됩니다. 만약 로봇이 0으로 응답하면, 해당 위치가 벽이고 로봇이 이동하지 않았음을 알 수 있습니다:

      
   #  
   D  
      
      

로봇을 동쪽으로 이동시키려면, 4를 보내세요. 응답 값이 1이면, 이동이 성공했음을 의미합니다.

   #  
   .D 
      
      

그런 다음 북쪽(1), 남쪽(2), 동쪽(4)으로 이동하려는 시도가 모두 0의 응답을 받았다고 해봅시다.

      
   ## 
   .D#
    # 
      

그럼 이제 수리 로봇이 막다른 골목에 있다는 것을 알 수 있습니다. 3을 입력하여 원래 위치로 되돌아 갑시다. (해당 위치가 지나다닐 수 있다는 것을 이미 알고 있기 때문에 1이라는 응답을 받을 것을 알 수 있습니다.)

      
   ## 
   D.#
    # 
      

이번에는 서쪽(3)은 0의 응답을 받고, 남쪽(2)은 1의 응답을 받고, 다시 남쪽(2)은 0의 응답을 받고, 마지막으로 서쪽(3)은 2의 응답을 얻었다고 가정해봅시다.

      
   ## 
  #..#
  D.# 
   #  

이제 응답으로 2를 받았기 때문에, 당신은 로봇이 산소 시스템을 찾았다는 것을 알 수 있습니다! 이 예에서는, 수리 로봇의 시작 위치에서 최소 두 번만에 도착할 수 있었습니다.

수리 로봇을 시작 위치에서 산소 시스템 위치로 이동하는 데 필요한 이동 명령의 최소 수는 얼마입니까?

Part 2

당신은 빠르게 산소 시스템을 고쳤습니다. 구역에 산소가 점점 차고 있습니다.

복구된 산소 시스템이 있는 구역부터 산소가 차기 시작합니다. 이미 산소가 차있는 구역에 인접한 모든 열려있는 구역으로 산소가 확산되는데 1분이 소요됩니다. 대각선으로 붙어있는 구역은 인접하지 않습니다.

위 예시에서, 당신은 로봇을 사용해 모든 지역을 완전히 탐색했으며, 다음과 같은 지도를 얻었다고 가정해봅시다. (현재 산소가 차있는 구역은 O으로 표시됩니다.)

 ##   
#..## 
#.#..#
#.O.# 
 ###  

처음에는 산소가 포함된 유일한 구역은 복구된 산소 시스템이 위치한 구역 뿐입니다. 그러나 1분이 지나면, 산소가 위치한 구역과 인접한 모든 열린(.) 지역에 산소가 퍼집니다.

 ##   
#..## 
#.#..#
#OOO# 
 ###  

2분이 지나면 지도는 다음과 같이 표시할 수 있습니다.

 ##   
#..## 
#O#O.#
#OOO# 
 ###  

3분 후

 ##   
#O.## 
#O#OO#
#OOO# 
 ###  

그리고 마지막으로 4분이 지나면 전체 구역이 산소로 가득 차게 됩니다.

 ##   
#OO## 
#O#OO#
#OOO# 
 ###  

따라서 이 예에서 모든 구역에 산소를 채워지는데 4분이 걸립니다.

수리 로봇을 사용하여 해당 지역의 완전한 지도를 얻으십시오. 모든 구역에 산소를 채우는 데 몇 분이 걸립니까?