로그인가입
문제 목록 / A013

막내

100점케이스 20출제 dongbinna
10월 30일에 올라온 문제입니다.
푼 사람 1명시도한 사람 1명제출 1건푼 분들은 평균 1.0번 만에
토론제출 내역 1

문제

N×N 크기의 집에 네 명의 형제가 있다. 막내는 형들을 좋아해서, 아침에 일어나면 첫째, 둘째, 셋째 형에게 차례대로 아침 안부를 묻는다. 초기에 네 형제는 모두 서로 다른 칸에 존재한다.

구체적으로 막내는 초기에 자신이 있는 위치에서 첫째, 둘째, 셋째의 위치를 차례대로 방문한 뒤에 원래의 위치로 돌아온다. 막내는 현재 위치에서 1초마다 인접한 상, 하, 좌, 우 위치로 이동할 수 있으며, 이동하는 과정에서는 한 칸에 여러 명이 존재할 수 있다. 또한, 특정한 형에게 안부를 묻기 위해서는 해당 형이 있는 동일한 격자 위치까지 도달해야 한다.

막내가 모든 형들에게 차례대로 도달하여 안부를 물어 본 뒤에 다시 원래의 위치로 돌아오기까지 걸리는 최소 시간을 계산하는 프로그램을 작성하여라.

예를 들어 N=6인 상황을 확인해 보자. 격자의 값 중에서 0은 아무 것도 없는 빈 칸을 의미하며, 1은 첫째가 있는 칸, 2는 둘째가 있는 칸, 3은 셋째가 있는 칸, 4는 막내가 있는 칸을 의미한다.

000000
040000
000200
000000
000010
030000

각 칸을 (행, 열)의 형태로 위치를 나타내고, 행과 열의 번호는 0부터 시작한다고 가정하자. 현재 상황에서는 막내가 (1, 1) → (4, 4) → (2, 3) → (5, 1) → (1, 1) 순서대로 이동하는 것이 최선이므로, 총 18(6 + 3 + 5 + 4)초의 시간이 소요된다. 따라서 본 예시에서의 정답은 18이다.

입출력 예시

예시 1

입력

6, [[0, 0, 0, 0, 0, 0], [0, 4, 0, 0, 0, 0], [0, 0, 0, 2, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0], [0, 3, 0, 0, 0, 0]]

출력

18

예시 2

입력

4, [[0, 1, 0, 0], [0, 2, 0, 0], [0, 0, 0, 0], [0, 4, 0, 3]]

출력

10

입력 조건

  • 가장 먼저 집의 크기 N이 주어진다. N은 3 이상 100 이하의 자연수다.

  • 이어서 행과 열의 길이가 각각 N인 2차원 배열 형태의 집 정보 배열 house가 주어진다. 격자의 값 중에서 0은 아무 것도 없는 빈 칸을 의미하며, 1은 첫째가 있는 칸, 2는 둘째가 있는 칸, 3은 셋째가 있는 칸, 4는 막내가 있는 칸을 의미한다.

출력 조건

  • 막내가 모든 형들에게 차례대로 도달하여 안부를 물어 본 뒤에 다시 원래의 위치로 돌아오기까지 걸리는 최소 시간을 반환하여라.

요구사항

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

예시

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

입력
기대 출력
6, [[0, 0, 0, 0, 0, 0], [0, 4, 0, 0, 0, 0], [0, 0, 0, 2, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0], [0, 3, 0, 0, 0, 0]]

18
4, [[0, 1, 0, 0], [0, 2, 0, 0], [0, 0, 0, 0], [0, 4, 0, 3]]

10
10, [[0, 0, 0, 4, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 2, 0, 0, 0, 0, 0]]
28
54, [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

... 여기까지만 보여 드립니다 (전체 8,860자)
122
12, [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 2, 0, 4, 0, 0, 0, 0, 0], [3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
22

참고 사항

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

원본에서 모의고사 5회 1번입니다.

풀이

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

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

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

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

이 문제를 푼 사람

시간은 푸는 데 걸린 시간입니다. 입력을 읽는 시간은 푸는 분이 어쩔 수 없는 값이라 빼고 셉니다. 그리고 이 값은 각자 기기가 적어 보내는 값이라, 어느 기기에서 쟀는지 같이 적어 둡니다.

1bampal219ms414자파이썬Windows NT 10.0 / Chrome/156.0.0.0 / 8코어 / 16GB

입력을 읽는 데 11ms (순위에서 뺀 시간입니다)

이 분이 코드를 비공개로 두셨습니다.