문제 설명
m × n 크기의 격자 상자가 주어져 있다고 가정해 보겠습니다. 각 칸에는 대각선 방향으로 기울어진 판이 하나씩 놓여 있으며, 판은 왼쪽 위 → 오른쪽 아래 방향이거나 오른쪽 위 → 왼쪽 아래 방향입니다. 상자 맨 윗줄에서 공을 하나씩 넣었을 때, 그 공이 상자 바닥까지 무사히 도달하는지 확인해야 합니다.
격자는 행렬 형태로 주어집니다. 칸의 값이 1이면 해당 판은 왼쪽 위에서 오른쪽 아래로 향하고, 값이 -1이면 오른쪽 위에서 왼쪽 아래로 향합니다. n개의 공을 상자에 넣을 때, 각 공이 최종적으로 빠져나가는 열 번호를 구하되, 바닥에 도달하지 못하는 공은 -1로 표시해야 합니다.
3×3 격자 상자 예시
예를 들어 입력 행렬이 다음과 같다면,
| 1 | 1 | 1 | -1 |
| -1 | 1 | 1 | -1 |
| 1 | -1 | -1 | 1 |
| 1 | -1 | 1 | -1 |
출력은 [-1, -1, -1, -1]이 됩니다. 즉, 어떤 공도 바닥에 도달하지 못합니다.
풀이 접근 방법
각 공의 위치를 한 행씩 내려가며 시뮬레이션하면 됩니다. 공은 현재 칸의 판 방향에 따라 좌우로 밀려나는데, 다음 두 가지 경우에는 바닥에 도달하지 못합니다.
경계 밖으로 밀려나는 경우: 공이 격자의 왼쪽(x < 0) 또는 오른쪽(x ≥ j) 경계 밖으로 굴러 떨어지는 경우
V자 함정에 걸리는 경우: 인접한 두 칸의 판이 서로 마주 보게 배치되어(예: 1 다음에 -1) 공이 두 판 사이에 끼이는 경우
이를 의사 코드로 표현하면 다음과 같습니다.
i := 행렬 mat의 행 개수
j := 행렬 mat의 열 개수
res := 결과를 저장할 새로운 리스트
val을 0부터 j-1까지 반복합니다.
x := val (공이 시작되는 열)
r을 0부터 i-1까지 반복합니다.
s := mat[r][x] (현재 칸의 판 방향 저장)
x := x + mat[r][x] (판 방향에 따라 공을 이동)
만약 x < 0 또는 x ≥ j 또는 mat[r][x] ≠ s라면:
res의 끝에 -1을 추가합니다.
반복문을 탈출합니다.
안쪽 반복문이 break 없이 정상 종료되면, res의 끝에 x를 추가합니다.
res를 반환합니다.
참고로 파이썬의 for-else 문법에서 else 블록은 반복문이 break 없이 모두 실행된 경우에만 수행됩니다. 따라서 공이 끝까지 내려간 경우에만 else 블록이 실행되어 최종 열 번호가 기록됩니다.
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(mat):
i, j = map(len, (mat, mat[0]))
res = []
for val in range(j):
x = val
for r in range(i):
s = mat[r][x]
x += mat[r][x]
if x < 0 or x >= j or mat[r][x] != s:
res += [-1]
break
else:
res += [x]
return res
print(solve([[1, 1, 1, -1], [-1, 1, 1, -1], [1, -1, -1, 1],[1, -1, 1, -1] ]))
입력
[[1, 1, 1, -1], [-1, 1, 1, -1], [1, -1, -1, 1],[1, -1, 1, -1] ]
출력
[-1, -1, -1, -1]
복잡도 분석
시간 복잡도는 O(m × n)입니다. 각 공마다 최대 m개의 행을 거치며, 총 n개의 공을 처리하기 때문입니다. 공간 복잡도는 결과 리스트를 제외하면 O(1)로, 추가 메모리 사용 없이 해결할 수 있습니다.