[BOJ/Python] 16173_점프왕 쩰리 (Small) || DFS

16173번: 점프왕 쩰리 (Small)

문제 설명

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

1. ‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.
2. ‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.
3. ‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.
4. ‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.
5. ‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있는 수 만큼이다. 칸에 쓰여 있는 수 초과나 그 미만으로 이동할 수 없다.

새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

입력)

입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 3)이 주어진다.
입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.
게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

출력)

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

예제)

❕ 문제 풀이

2차원 배열로 그래프의 연결 관계를 표현하는 방식을 이용했다.
1. 탐색할 노드를 방문 처리 한다.
2. 이동 가능 거리를 계산하여 범위에 벗어나는지 확인한다. 벗어나지 않는다면 탐색
+ 이미 방문했는지, 값이 -1로 승리지점에 해당하는지를 확인한다.

입력

global check
check = 0

n = int(input())
arr = []
visited = [[False] * n for _ in range(n)]
for _ in range(n):
    arr.append(list(map(int, input().split())))

dfs(0, 0, arr, visited)

2차원 배열로 그래프의 연결을 표현해주었다.
방문 확인을 할 visited도 2차원 배열로 모두 False로 초기화해준다.
dfs함수에 인덱스를 넣어주어 접근할 수 있도록 한다.
게임에서 승리했는지 확인해주기 위해 전역변수인 check를 선언 및 초기화를 해준다.

1.

# 방문했는지 확인하기
if visited[x][y]:
    return

visited[x][y] = True

해당하는 곳을 방문한 적이 있는지 확인한다.

2.

# 범위를 벗어나는지 확인하기
if arr[x][y] + y < len(arr):
    dfs(x, arr[x][y] + y, arr, visited)
if arr[x][y] + x < len(arr):
    dfs(arr[x][y] + x, y, arr, visited)

입력받은 이동 가능 거리를 현재의 위치의 행과 열에 더해주면서 주어진 멥에서 벗어나는지 확인한다.
벗어나지 않는다면, 해당 위치로 DFS 함수가 실행되도록 한다.

3.

# 승리지점인지 확인하기
if arr[x][y] == -1:
    check = 1
    return

승리지점인지 확인하고, 전역변수인 check의 값을 1로 설정해주고 리턴한다.

4.

if check == 1:
    print("HaruHaru")
else:
    print("Hing")

check를 통해 승리지점에 도달했는지에 따라 출력해준다.

---

✅ [ CODE ]

def dfs(x, y, arr, visited):
    global check
    # 방문했는지 확인하기
    if visited[x][y]:
        return

    visited[x][y] = True

    # 승리지점인지 확인하기
    if arr[x][y] == -1:
        check = 1
        return

    # 범위를 벗어나는지 확인하기
    if arr[x][y] + y < len(arr):
        dfs(x, arr[x][y] + y, arr, visited)
    if arr[x][y] + x < len(arr):
        dfs(arr[x][y] + x, y, arr, visited)


global check
check = 0
n = int(input())
arr = []
visited = [[False] * n for _ in range(n)]
for _ in range(n):
    arr.append(list(map(int, input().split())))

dfs(0, 0, arr, visited)

if check == 1:
    print("HaruHaru")
else:
    print("Hing")

전역변수의 경우 함수 내부에서도 선언해주어야 한다..