로그인가입
문제 목록 / A020

벽 피하기

200점케이스 14출제 dongbinna
10월 30일에 올라온 문제입니다.
토론제출 내역

문제

벽 피하기 게임에서는 N×M 크기의 격자가 주어진다. 격자의 각 칸에 대하여 0은 빈 칸, 1은 벽, 2는 플레이어의 위치를 의미한다. 플레이어는 1명이다.

플레이어는 초기에 항상 가장 아래 행(줄)의 한 위치에 존재한다. 플레이어는 매 번 (1) 가만히 있거나, (2) 왼쪽으로 한 칸 이동하거나, 혹은 (3) 오른쪽으로 한 칸 이동할 수 있다. 플레이어가 이동한 뒤에는 위에서부터 존재하는 모든 벽이 한 칸씩 아래로 내려온다.

구체적으로 1초동안 ① 초기 플레이어가 먼저 행동하고, ② 이후에 모든 벽에 해당하는 칸이 한 칸씩 아래로 내려온다. 플레이어가 벽에 부딪힌다면 즉시 게임이 종료되며, 부딪히지 않은 경우 플레이어가 생존한 시기가 1초만큼 증가하는 것으로 간주한다.

벽이 내려온 직후에 플레이어가 살아남았을 경우 1초만큼 생존한 시간이 증가한 것으로 간주하기 때문에, 만약 처음부터 플레이어가 존재하는 위치의 윗줄의 칸들이 모두 벽으로 완전히 가로막혀있다면 정답으로는 0초를 출력해야 할 것이다. 예를 들어 다음과 같은 예시가 있다.

1111111111
0000020000

플레이어는 벽 피하기 게임으로부터 최대한 오랜 시간을 버티는 것이 목표다. 전체 행(줄)의 수가 최대 N이라는 점에서 최대로 버틸 수 있는 시간은 N-1초이다. 결과적으로 플레이어가 최적의 움직임을 보인다고 했을 때, 플레이어가 생존 가능한 최대 시간을 계산하는 프로그램을 작성하여라.

예를 들어 N=9, M=10인 상황을 가정하자. N×M 크기의 각 공간에 대한 정보는 아래의 2차원 배열과 같다.

0011111111
0001111111
0000011111
1111001111
0000000000
0000000000
1001000011
0001111111
0002000000

초기 3초 동안 플레이어가 "왼쪽 → 가만히 → 가만히" 순서대로 행동한다면, 게임 시작 이후 3초 뒤에 전체 공간의 형태는 다음과 같을 것이다.

0011111111
0001111111
0000011111
1111001111
0000000000
0020000000

이후에 "오른쪽 → 오른쪽 → 가만히" 순서대로 행동한다면, 게임 시작 이후 6초 뒤에 전체 공간의 형태는 다음과 같을 것이다.

0011111111
0001111111
0000211111

현재 상황에서는 플레이어가 어떤 행동을 취해도 벽에 부딪혀 게임이 종료된다. 결과적으로 현재 예시에서는 플레이어가 최적의 행동을 취했을 때 최대 6초까지 생존이 가능한 것으로 이해할 수 있다.

초기 게임 보드 판의 정보가 2차원 배열 형태로 주어졌을 때, 플레이어가 생존 가능한 최대 시간을 반환하는 프로그램을 작성하여라.

입출력 예시

예시 1

입력

9, 10, [[0, 0, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 2, 0, 0, 0, 0, 0, 0]]

출력

6

입력 조건

  • 가장 먼저 벽 피하기 게임을 진행할 보드 판에 대한 크기 정보 N과 M이 주어진다. N과 M은 3보다 크거나 같고 100보다 작거나 같은 자연수다.

  • 이어서 벽 피하기 게임을 진행할 보드 판에 대한 정보가 담긴 N×M 크기의 2차원 배열 board가 주어진다. 격자의 각 칸에 대하여 0은 빈 칸, 1은 벽, 2는 플레이어의 초기 위치를 의미한다. 플레이어는 항상 1명이며, 플레이어는 초기에 가장 아래 행(줄)의 한 위치에 존재한다.

출력 조건

  • 플레이어가 최선을 선택을 함으로써 생존 가능한 최대 시간을 반환한다.

요구사항

  • solution(N, M, board) 함수를 만들고 답을 반환해야 합니다
  • 쓸 수 있는 말은 파이썬, 자바스크립트입니다
  • 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
  • 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
  • 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
  • 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
  • 케이스는 14개이고, 그 가운데 4개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
  • 케이스 14개를 전부 통과해야 해결입니다.
문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

예시

공개 케이스 4개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 14개를 전부 통과해야 해결입니다.

입력
기대 출력
9, 10, [[0, 0, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 0, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 2, 0, 0, 0, 0, 0, 0]]

6
10, 82, [[0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0], [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0], [0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0], [0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 

... 여기까지만 보여 드립니다 (전체 2,488자)
2
30, 50, [[0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0], [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0], [1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1], [1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1], [0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0], [1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 

... 여기까지만 보여 드립니다 (전체 4,568자)
11
92, 92, [[1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0], [1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0], [0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1], [1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1], [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 

... 여기까지만 보여 드립니다 (전체 25,584자)
6

참고 사항

풀이에 도움이 되는 배경입니다. 지켜야 하는 규격은 위의 입출력 조건과 요구사항에 있습니다.

원본에서 모의고사 7회 2번입니다.

풀이

코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.

0자1줄메모리 256MB (적어만 둡니다)기준 1.0ms

제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.

공개 케이스 4개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.

이 문제를 푼 사람

아직 없습니다. 첫 번째가 되실 수 있습니다.