16173 점프왕 쩰리 파이썬(재시도 -0)
문제
‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.
- ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
- ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
- ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
- ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
- ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.
새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!
입력
입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.
입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.
게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.
출력
‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.
마지막 좌표까지 도달할 수 있는지 여부를 찾는 문제다.
생각한 입력 및 변수로는
1. 맵 크기 N
2.게임판 맵 배열 :arr
이렇게 2개를 생각하고, bfs나 dfs를 추가하는걸 생각했다.
생각한 흐름으로는
need_visit에 [0,0]을 넣고 시작해서
하나씩 오른쪽에서 pop하는 스택을 생각했고,
오른쪽으로 가는경우와 아래로 가는 경우 2가지를 나눠서 생각하고
-1이면 True를 리턴하게 했다.
그러나 85%에서 시간초과가 발생했다.
결국 헤메다가 다른 분의 풀이를 참고해보았다.
내가 놓쳤던 부분은 방문배열을 따로 만들어서 방문했던 곳은 스택에 넣는 부분이었다.
기존 그래프 탐색에서는 방문한 순서를 큐에 저장했는데, 이문제에서는 굳이 순서가 필요하지는 않아서
배제했었다.
하지만 방문했는지 여부를 체크하는 배열이 없어서 계속 중복으로 계산하는 부분이 생겼다.
이부분을 계산하는데 시간 초과가 뜬 것 같다.
더 추가할만 한 부분은 방문여부를 체크하는 배열과 이동배열( 이부분은 사실 최적화에 가까운것 같다.)
이다.
그 중복을 제거해주는 배열 하나때문에 풀지 못했다.
입력
(N, arr)
방문배열
def jump():
need_visit과 방문여부 확인 (visited)선언, 첫원소 삽입
while need_visit에 원소가 없을 때까지:
원소 인덱스 추출
해당 인덱스의arr값이 -1이면 True리턴
jum=이동배열에서 이동할 배수 , arr값
for i in range(2):
이동배열에 따라 2가지 이동할 좌표(우, 하)를 만들고,
좌표마다 범위내에 있고, 방문하지 않았으면
방문 여부 =1 , 스택에 append
return False
import sys
input=sys.stdin.readline
#n입력
N=int(input())
#게임 배열 입력
arr=[ list(map(int,input().split())) for _ in range(N)]
dx=[1,0]
dy=[0,1]
def jump():
need_visit=[[0,0]]
visited=[[0]* N for _ in range(N)]
while need_visit:
x, y = need_visit.pop(0)
if arr[x][y] == -1:
return True
jum=arr[x][y]
for i in range(2):
nx=x+dx[i]*jum
ny = y + dy[i] * jum
if 0 <= nx < N and 0 <= ny < N and visited[nx][ny]==0:
visited[nx][ny]=1
need_visit.append([nx,ny])
return False
if jump()==True:
print("HaruHaru")
else:
print("Hing")