Binding of Isaac

Binding of Isaac은 로그라이크 슈팅 게임으로 무작위로 생성되는 던전 속에서 몬스터를 잡고 성장하며 보스를 잡는 게임이다. 한 번 던전을 생성하고, 생성한 던전을 클리어할 수 있는지 판별하는 프로그램을 작성해 보자.

시드
- 시드는 길이가 $9$인 문자열이다. $5$번째 문자는 -이고 나머지 문자는 대문자 알파벳과 숫자로 총 $36$가지의 문자로 구성되어 있다.
- $5$번째 문자를 제거한 뒤 앞 문자 $4$개와 뒤 문자 $4$개를 그대로 이어 붙인다. 이 문자열을 $0$-$9$, $A$-$Z$ 순서로 $36$진법으로 표현했을 때, $10$진법으로 변환한 값을 정수 $S_1$라 정의한다.
난수 함수
- rand()
  - 유사 난수 생성기 함수이며, 선형 합동 생성기를 활용한다.
  - rand() 함수를 $i$번째로 호출하면 $S_{n + 1} = (aS_n + c) \bmod m$ 식에 따라 $S_i$를 반환한다.
    - $S_1$은 위 시드 설명에서 정의했음에 유의하라. 만약 $S_1$이 $m$보다 크면 $S_1$ 대신 $S_1$을 $m$으로 나눈 나머지를 $S_1$로 재정의한다.
  - 이때 $a = 1\,103\,515\,245$, $c = 12\,345$, $m = 2^{31}$이다.
- randInt($l$, $r$)
  - $l$ 이상 $r$ 이하의 임의의 정수 하나를 반환하는 함수이다.
  - randInt($l$, $r$)를 호출하면 $l$에 rand()$\bmod (r - l + 1)$을 더한 값을 반환한다.
- chance($p$)
  - $p$% 확률로 True를 반환하는 함수이다.
  - chance($p$)를 호출하면 randInt($1$, $100$) $\le p$의 논리 연산 결과를 반환한다.
- choice($\text{arr}$)
  - 배열 $\text{arr}$에 있는 임의의 원소 하나를 반환하는 함수이다.
  - choice($\text{arr}$)을 호출하면 배열 $\text{arr}$의 randInt($0$, $\text{arr}$의 길이 $-\ 1$)번째 원소를 반환한다.
    - 원소가 $N$개인 배열은 첫 번째 원소가 $0$번째이고, 마지막 원소가 $N - 1$번째 원소이다.
던전 생성
- 던전은 아래의 단계 순서대로 생성하며, rand() 호출 순서에 따라 결과가 달라질 수 있음에 유의하라.
- 배열에서 원소를 제거할 때, 제거하지 않은 나머지 원소들의 순서는 유지된다.
- 1단계
  - 던전에 활용할 방 개수 $N$을 randInt($10$, $20$) 값으로 정의한다. 이 과정에서 rand() 함수는 $R_1$번 호출된다. $(R_1 = 1)$
  - 던전 생성 1단계를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{1}R_i$번 호출되었다.
- 2단계
  - 크기가 $9 \times 9$이고 칸이 총 $81$개인 격자 보드를 생성한다. 좌측 최상단의 좌표가 $(0, 0)$이고 우측 최하단의 좌표가 $(8, 8)$이다. $(x, y)$는 $x$행 $y$열을 의미한다.
  - 2단계에서 생성된 방은 배열 $\text{room}$에 순서대로 넣는다.
  - $(4, 4)$ 위치에 시작방을 생성한다. (배열 $\text{room}$에도 시작방이 담긴다.)
  - 아래 과정을 총 $N$개(시작방은 제외)의 방을 생성할 때까지 반복한다.
    - 큐 $Q$에 choice($\text{room}$)의 값(방)을 넣는다.
    - 아래 과정을 큐 $Q$가 완전히 빌 때까지 반복한다.
      - 큐 $Q$에서 가장 먼저 넣었던 방을 꺼낸다.
      - 그 방의 좌표 중심으로 동남서북 순서로 인접한 칸에다 새로운 방 생성을 시도한다.
        
        $N$개(시작방은 제외)의 방을 생성했다면 방 생성 시도를 중지한다.
        
        보고 있는 칸에 이미 방이 생성되어 있다면 방 생성에 실패한다.
        
        방을 생성할 칸에서 인접하는 칸 중 이미 생성된 방이 $2$개 이상이라면 방 생성에 실패한다.
        
        위 $2$개의 조건에서 실패하지 않았을 때, chance($50$)를 호출한 값이 False면 방 생성에 실패한다.
        
        위 $3$개의 조건에서 실패하지 않았을 때, 방 생성에 성공하며 큐 $Q$에 방금 생성된 방을 넣는다. (배열 $\text{room}$에도 방금 생성된 방이 담긴다.)
  - 배열 $\text{room}$에서 시작방을 제거한다.
  - 방 생성 과정에서 rand() 함수는 $R_2$번 호출된다.
  - 던전 생성 2단계를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{2}R_i$번 호출되었다.
- 3단계
  - 배열 $\text{special}$은 배열 $\text{room}$에서 인접한 방의 개수가 $1$개인 방들을 생성된 순서대로 넣은 배열이다.
  - 일반방을 지정한다.
    - 배열 $\text{require}$은 $0$이 $10$개, $1$이 $9$개, $2$가 $8$개, ..., $8$이 $2$개, $9$가 $1$개가 순서대로 담긴 배열이다.
    - 배열 $\text{room}$에서 배열 $\text{special}$에 속하지 않은 방들을 생성된 순서대로 choice($\text{require}$)의 요구 공격력을 가진 일반방으로 지정한다.
    - 이 과정에서 rand() 함수는 $R_3$번 호출된다. $(R_3 =$ 배열 $\text{room}$에서 배열 $\text{special}$에 속하지 않은 방 개수$)$
    - 일반방 지정을 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{3}R_i$번 호출되었다.
  - 보스방을 지정한다.
    - 배열 $\text{boss}$는 배열 $\text{special}$에서 인접한 칸이 시작방이 아닌 방들이 생성된 순서대로 넣은 배열이다.
    - choice($\text{boss}$)을 보스방으로 지정한다.
      - 지정된 보스방을 배열 $\text{special}$에서 제거한다.
    - 이 과정에서 rand() 함수는 $R_4$번 호출된다. $(R_4 = 1)$
    - 보스방 지정을 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{4}R_i$번 호출되었다.
  - 비밀방을 지정 시도한다.
    - 만약 배열 $\text{special}$가 비었다면 비밀방 지정 시도를 중지한다.
    - 비밀방은 항상 지정에 성공한다.
    - 지정에 성공했다면 choice($\text{special}$)을 비밀방으로 지정한다.
      - 지정된 비밀방을 배열 $\text{special}$에서 제거한다.
    - 이 과정에서 rand() 함수는 $R_5$번 호출된다. $($비밀방이 지정되었다면 $R_5 = 1$, 지정되지 않았다면 $R_5 = 0)$
    - 비밀방 지정 시도를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{5}R_i$번 호출되었다.
  - 보물방을 지정 시도한다.
    - 만약 배열 $\text{special}$가 비었다면 보물방 지정 시도를 중지한다.
    - 보물방은 항상 지정에 성공한다.
    - 지정에 성공했다면 choice($\text{special}$)을 보물방으로 지정한다.
      - 지정된 보물방을 배열 $\text{special}$에서 제거한다.
    - 이 과정에서 rand() 함수는 $R_6$번 호출된다. $($보물방이 지정되었다면 $R_6 = 1$, 지정되지 않았다면 $R_6 = 0)$
    - 보물방 지정 시도를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{6}R_i$번 호출되었다.
    - $N$이 $15$ 이상이면 보물방을 한 번 더 지정 시도한다.
      - 만약 배열 $\text{special}$가 비었다면 보물방 추가 지정 시도를 중지한다.
      - chance($25$)를 호출한 값이 False면 보물방 추가 지정에 실패하고, 그렇지 않으면 성공한다.
      - 지정에 성공했다면 choice($\text{special}$)을 보물방으로 추가 지정한다.
        
        추가 지정된 보물방을 배열 $\text{special}$에서 제거한다.
      - 이 과정에서 rand() 함수는 $R_7$번 호출된다. $($보물방이 추가 지정되었다면 $R_7 = 2$, 추가 지정되지 않았다면 $R_7 = 1)$
      - 보물방 추가 지정 시도를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{7}R_i$번 호출되었다.
  - 상점방을 지정 시도한다.
    - 만약 배열 $\text{special}$가 비었다면 상점방 지정 시도를 중지한다.
    - 만약 $N$이 $15$ 이하라면 상점방 지정에 성공한다. 그렇지 않고 chance($66$)를 호출한 값이 True면 상점방 지정에 성공한다. 그렇지 않으면 실패한다.
    - 지정에 성공했다면 choice($\text{special}$)을 상점방으로 지정한다.
      - 지정된 상점방을 배열 $\text{special}$에서 제거한다.
    - 이 과정에서 rand() 함수는 $R_8$번 호출된다. $($$N$이 $15$ 이하라면 $R_8 = 1$, $N$이 $15$ 초과이고 상점방이 지정되었다면 $R_8 = 2$, $N$이 $15$ 초과이고 상점방이 지정되지 않았다면 $R_8 = 1)$
    - 상점방 지정 시도를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{8}R_i$번 호출되었다.
  - 악마방 혹은 천사방을 생성 시도한다.
    - chance($20$)를 호출한 값이 True면 악마방 혹은 천사방 생성 시도에 성공한다. 그렇지 않으면 실패한다.
    - 배열 $\text{reward}$은 보스방에서 동서남북 순서대로 인접한 칸이 담긴 배열이다.
    - 배열 $\text{reward}$에서 다음 조건 중 하나라도 만족하는 칸들을 제거한다.
      - 해당 칸 $(x_j, y_j)$에 방이 이미 존재한다.
      - 생성된 모든 방 $(x_k, y_k)$ 중 $x_k$의 최솟값을 $x_m$, $x_k$의 최댓값을 $x_M$, $y_k$의 최솟값을 $y_m$, $y_k$의 최댓값을 $y_M$라 할 때, $x_m \le x_j \le x_M$가 아니거나 $y_m \le y_j \le y_M$가 아니다.
    - 생성 시도에 성공했다면 choice($\text{reward}$)에 방을 생성한다.
      - chance($50$)를 호출한 값이 True면 악마방으로 지정한다. 그렇지 않으면 천사방으로 지정한다.
    - 이 과정에서 rand() 함수는 $R_9$번 호출된다. $($악마방 혹은 천사방이 생성되었다면 $R_9 = 3$, 생성되지 않았다면 $R_9 = 1)$
    - 악마방 혹은 천사방 생성 시도를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{9}R_i$번 호출되었다.
  - 희생방을 지정 시도한다.
    - 만약 배열 $\text{special}$가 비었다면 희생방 지정 시도를 중지한다.
    - 만약 생성된 방 중 천사방이 존재하면 희생방 지정에 성공한다. 그렇지 않고 chance($14$)를 호출한 값이 True면 희생방 지정에 성공한다. 그렇지 않으면 실패한다.
    - 지정에 성공했다면 choice($\text{special}$)을 희생방으로 지정한다.
      - 지정된 희생방을 배열 $\text{special}$에서 제거한다.
    - 이 과정에서 rand() 함수는 $R_{10}$번 호출된다. $($생성된 방 중 천사방이 존재하면 $R_{10} = 1$, 생성된 방 중 천사방이 존재하지 않고 희생방이 지정되었다면 $R_{10} = 2$, 생성된 방 중 천사방이 존재하지 않고 희생방이 지정되지 않았다면 $R_{10} = 1)$
    - 희생방 지정 시도를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{10}R_i$번 호출되었다.
  - 저주방을 지정 시도한다.
    - 만약 배열 $\text{special}$가 비었다면 저주방 지정 시도를 중지한다.
    - 만약 생성된 방 중 악마방이 존재하지 않으면 저주방 지정에 실패한다.
    - 위 조건에서 실패하지 않았을 때, chance($50$)를 호출한 값이 True면 저주방 지정에 성공한다. 그렇지 않으면 실패한다.
    - 지정에 성공했다면 choice($\text{special}$)을 저주방으로 지정한다.
      - 지정된 저주방을 배열 $\text{special}$에서 제거한다.
    - 이 과정에서 rand() 함수는 $R_{11}$번 호출된다. $($생성된 방 중 악마방이 존재하지 않으면 $R_{11} = 0$, 생성된 방 중 악마방이 존재하고 저주방이 지정되었다면 $R_{11} = 2$, 생성된 방 중 악마방이 존재하고 저주방이 지정되지 않았다면 $R_{11} = 1)$
    - 저주방 지정 시도를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{11}R_i$번 호출되었다.
  - 일반방을 추가 지정한다.
    - 만약 배열 $\text{special}$가 비었다면 일반방 추가 지정 시도를 중지한다.
    - 배열 $\text{special}$에 속한 방들을 생성된 순서대로 choice($\text{require}$)의 요구 공격력을 가진 일반방으로 추가 지정한다.
    - 이 과정에서 rand() 함수는 $R_{12}$번 호출된다. $(R_{12} =$ 배열 $\text{special}$의 원소 개수$)$
    - 일반방 추가 지정을 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{12}R_i$번 호출되었다.
  - 던전 생성 3단계를 마쳤을 때, rand() 함수는 총 $\sum_{i=1}^{12}R_i$번 호출되었다.
방 설명
- 플레이어는 이동하려는 방이 비밀방, 천사방, 악마방이 아니면 자신이 있는 방에서 인접한 방으로 자유롭게 이동할 수 있다.
- 시작방
  - 플레이어는 해당 방에서 게임을 시작하게 된다.
  - 게임 시작 시 상태는 아래와 같다.
    - 체력 : $6$
    - 공격력 : $1$
  - 게임 시작 시 아이템 상태는 아래와 같다.
    - 코인 : $0$개
    - 폭탄 : $3$개
    - 코인 개수와 폭탄 개수는 음의 정수가 될 수 없다.
- 일반방
  - 일반방은 요구 공격력을 가진다.
  - 플레이어가 일반방을 처음 입장하면 반드시 몬스터와 전투를 치러야 한다
  - 전투 과정에서 플레이어의 공격력이 일반방의 요구 공격력보다 낮으면 체력이 $1$ 감소한다.
    - 체력이 $1$ 감소하는 대신, 폭탄 $1$개를 소모하여 전투를 치를 수 있다.
  - 전투를 치른 뒤에 플레이어가 체력 $1$ 이상이라면 코인 $1$개를 획득한다.
  - 플레이어가 이미 방문했던 일반방을 다시 입장하면 아무 일도 일어나지 않는다.
- 보스방
  - 플레이어가 보스방을 처음 입장하면 반드시 보스와 전투를 치러야 한다
  - 공격력이 $10$ 이상이면 보스와의 전투에서 승리한다. 그렇지 않으면 체력이 $0$이 된다.
- 비밀방
  - 비밀방과 인접한 방에서 폭탄 $1$개를 소모하여 입장할 수 있다.
    - 이전에 비밀방을 한 번 방문한 적이 있다면, 더 이상 폭탄을 소모하지 않고 방문할 수 있다.
  - 플레이어가 비밀방에 처음 입장하면 체력과 공격력이 $2$ 상승하고, 코인 $2$개를 획득한다.
- 보물방
  - 플레이어가 보물방에 처음 입장하면 공격력이 $1$ 상승한다.
- 상점방
  - 코인 $2$개당 아이템 $1$개씩 구매할 수 있다.
  - 아이템은 두 종류가 있으며, 각각 무한정 구매할 수 있다.
    - 빨간 물약 : 체력이 $1$ 상승한다.
    - 파란 물약 : 공격력이 $1$ 상승한다.
- 악마방 & 천사방
  - 이동할 수 없는 가상의 방으로, 게임 플레이에 영향을 주지 않는다.
- 희생방
  - 플레이어가 희생방에 처음 입장하면 체력이 $2$ 감소하고 공격력이 $3$ 상승한다.
- 저주방
  - 플레이어가 저주방에 처음 입장하면 공격력이 $2$ 감소하고 코인 $3$개와 폭탄 $1$개를 획득한다.
게임 진행
- 플레이어가 체력이 $0$ 이하가 된다면 그 즉시 게임에 패배하고 종료된다.
- 플레이어가 보스와의 전투에서 승리하면 그 즉시 게임에 승리하고 종료된다.

Binding of Isaac

문제

입력

출력