[알고리즘]BOJ_16173_점프왕 쩰리(파이썬 dfs, 2차원 행렬로 입력받기, 2차원 리스트 만들기)

#문제 링크

https://www.acmicpc.net/problem/16173

16173번: 점프왕 쩰리 (Small)

 

#문제

https://www.acmicpc.net/problem/16173

문제
‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 
새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.

‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다.
‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다.
칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.
새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다.
하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 
이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다.
‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다.
‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

입력
입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.

입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.

게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 
나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

출력
‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이),
도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.

예제 입력 1
3
1 1 10
1 5 1
2 2 -1
예제 출력 1
HaruHaru
쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로,
(1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다.

예제 입력 2
3
2 2 1
2 2 2
1 2 -1
예제 출력 2
Hing
쩰리는 맨 왼쪽 위의 칸에서 출발하더라도 절대 게임의 승리 지점인 (3, 3)에 도달할 수 없다.

 

#답안

import sys
input=sys.stdin.readline


def dfs(x,y) :
    #영역을 벗어났거나 이미 방문을 했다면 return
    if x<=-1 or x>=N or y<=-1 or y>=N or visit[x][y]==1:
        return
    
    #방문한 곳의 이동 칸 수가 -1이라면 방문처리를 해주고 return 한다. 
    if graph[x][y] == -1 :
        visit[x][y] = 1
        return

    #방문했다고 표시해준다.
    visit[x][y]=1

    #상,하,좌,우를 요소 수만큼 점프하여 방문한다.
    dfs(x+graph[x][y],y)
    dfs(x-graph[x][y],y)
    dfs(x,y+graph[x][y])
    dfs(x,y-graph[x][y])



#게임 구역의 크기 N을 입력받는다.
N=int(input())

#게임판의 구역을 입력받는다. 2차원 리스트
graph=[list(map(int,input().split())) for _ in range(N)]

#방문여부를 저장할 visit 2차원 리스트를 만든다.
visit=[[0]*N for _ in range(N)]

#출발은 0,0에서 하므로 dfs(0,0)을 호출한다.
dfs(0,0)

#결과 출력
if visit[-1][-1] == 1 :
    print('HaruHaru')
else :
    print('Hing')

▲답안 설명

 

step01) 좌표 0,0부터 출발하므로 dfs(0,0)을 호출한다.
step02) dfs 함수 내에서는....
          dfs 종료조건1 - 좌표의 위치가 게임판의 범위를 벗어나거나, visit테이블에서 방문한 곳이라면 함수 return
          dfs 종료조건2 - 현재 좌표의 이동 칸 수가 -1이라면 visit테이블에 방문처리 하고 return 

          위의 종료조건 2가지에 해당하지 않는다면..

          방문처리visit에 해주고 상, 하, 좌, 우의 위치를 현재 좌표의 이동 칸 수 만큼 더해서 구해준 후 dfs를 호출한다.
step03) 모든 호출이 끝나고 visit테이블에서 -1위치에 방문표시가 되어있다면 HaruHaru출력, 그렇지 않다면 Hing출력          

 

+알아둘 것 

1. 입력조건이 아래와 같을 때 

3
1 1 10
1 5 1
2 2 -1

 

2. dfs 함수 내 아래 코드를 있는 것과 없는 것의 차이점

    if graph[x][y] == -1 :
        visit[x][y] = 1
        return

 

위의 코드가 있다면 

이동 칸수가 -1인 곳을 방문했을 때

방문처리를 해주고 return해서 함수를 빠져나감으로서 재귀 호출을 더 하지 않게 막아준다.

visit테이블이 [[1, 1, 1], [1, 0, 1], [1, 1, 0]] 인것으로 확인 가능

위의 코드가 없다면

방문 가능한 모든 곳을 방문하여 모두 방문하게 된다. 

visit테이블이 [[1, 1, 1], [1, 1, 1], [1, 1, 1]] 인것으로 확인 가능 

 

따라서 위의 코드를 추가해 속도를 조금 더 빠르게 해보았다. 

속도차이가 아주 크진 않지만 위의 코드를 추가했을 때 조금 더 빠르다 ㅎㅎ