16173번: 점프왕 쩰리(8 / 29) - 실버 4

문제

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

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

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

입력

입력의 첫 번째 줄에는 게임 구역의 크기 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)에 도달할 수 없다.

코드

# 1. 경계 조건
# 2. 0, 0에서 출발
# 3. + row, + colum만 이동 가능
# 4. 가장 오른쪽, 가장 아래칸에 도달하면 (-1) return
# 5. 이동조건은 해당 위치의 수만큼임

import sys
n = int(sys.stdin.readline())
# graph 인풋을 받음
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 방문 여부 체크
visited = [[False] * n for _ in range(n)]

def check_map(row, col):
    # 현재 위치를 출력
    print(f"Visiting: row={row}, col={col}, value={graph[row][col]}")

    if graph[row][col] == -1:
        print(f"Reached goal at row={row}, col={col}")
        return True

    # 현재 위치에서 이동할 수 있는 칸의 수
    jump = graph[row][col]

    # 오른쪽 이동이 가능하면 이동
    if col + jump < n and not visited[row][col + jump]:
        print(f"Trying to move right from row={row}, col={col} to row={row}, col={col + jump}")
        visited[row][col + jump] = True
        if check_map(row, col + jump):
            return True

    #  아래쪽 이동이 가능하면 이동
    if row + jump < n and not visited[row + jump][col]:
        print(f"Trying to move down from row={row}, col={col} to row={row + jump}, col={col}")
        visited[row + jump][col] = True
        if check_map(row + jump, col):
            return True

    return False

if check_map(0, 0):
    print('HaruHaru')
else:
    print("Hing")

코드 풀이

1. 입력으로 graph와 visited를 2차원 배열로 받는다.
   • graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
   • visited = [[False] * n for _ in range(n)]
2. check_map() 재귀함수를 정의한다.
   • 해당 위치에 방문 처리를 해준다.
   • 만약 해당 위치의 값이 -1이라면 True를 반환하여 재귀함수를 종료한다.
   • 이동할 수 있는 위치는 그래프의 해당 숫자이므로 그 값을 jump 변수에 담아준다.
   • 오른쪽과 아래로만 이동이 가능하므로 2개의 조건문을 설정해준다.
     • 오른쪽의 경우
       1. col + jump가 graph의 경계 안쪽에 있는가?
       2. visited[row][col + jump]가 방문이 되지 않았나?
          • if check_map(row, col + jump) 로 다시 재귀함수를 호출한다.
            • return값이 True라면 다시 return True로 재귀함수를 종료한다.
            • retrun값이 False라면 아래 row 조건으로 넘어간다.
     • 아래쪽의 경우
       1. row + jump가 graph의 경계 안쪽에 있는가?
       2. visited[row + jump][col]이 방문되지 않았나?
          • if check_map(row + jump, col) 로 다시 재귀함수를 호출한다.
            • return값이 True라면 다시 return True로 재귀함수를 종료한다.
            • return값이 False라면 return False를 받아 재귀함수를 종료한다.
   • 함수를 0, 0자리부터 시작하기 위해 재귀함수를 호출해준다. 만약 해당 재귀함수의 반환값이 True라면 print(’HaruHaru) 를 호출한다.
   • 아니라면 print(’Hing’) 을 호출한다.

핵심 포인트

1. 해당 문제의 경우 전체의 배열을 한번씩 순회해야 하는 문제가 아니라, 해당 목표 지점으로 가는 경로를 탐색해야 하는 문제이므로 단일 재귀함수를 호출하는 방향으로 문제에 접근한다.
2. 재귀함수를 종료하기 위해 return True 또는 False를 사용한다.
   • 해당 함수를 if로 함께 출력하고 목표 지점에 도달한 경우 return True를 반환하게 함으로써 재귀함수를 종료하게 한다.
   • 목표 지점에 도달하지 못하는 경우 return False를 반환하게 함으로써 재귀함수를 종료하게 한다.
3. 0, 0부터 시작해야하기 때문에 해당 재귀함수에 인자로 0, 0을 넣어준다.

DFS(깊이 우선 탐색) 문제에서 2중 For문을 사용하는 경우

상황: 주로 그래프나 2차원 배열 전체를 탐색해야 할 때, 예를 들어 섬의 개수를 세거나, 연결된 영역을 탐색하는 경우

이유: 모든 위치에서 탐색을 시작할 필요가 있다. 즉, 배열의 각 위치를 하나씩 검사하면서, 아직 방문하지 않은 새로운 영역을 발견하면 그곳에서부터 DFS를 시작한다.

2중 for문의 역할: 배열의 모든 위치를 방문하기 위해 사용된다.

DFS(깊이 우선 탐색) 문제에서 반복 루프를 사용하지 않는 경우

상황: 특정 시작점에서 목표 지점으로 가는 경로를 탐색해야 할 때, 예를 들어 시작점이 정해져 있고, 그 위치에서 DFS를 통해 목표 지점에 도달할 수 있는지를 탐색한다.

이유: 문제에서 시작점이 고정되어 있고, 그곳에서만 탐색을 시작하기 때문에 굳이 모든 위치를 방문할 필요가 없다. 한번의 DFS 호출로 가능한 모든 경로를 탐색하여 목표 지점에 도달할 수 있는지 확인한다.

반복루프 불필요: 단일 재귀 호출만으로도 문제를 해결할 수 있다. 이 경우 루프는 필요하지 않다.

요약

• 반복 루프를 사용하는 경우: 문제에서 배열 전체를 탐색해야 하거나, 각 위치에서 탐색을 시작해야 하는 경우.
  • 이때 이중 for문을 사용해서 모든 위치를 방문하고, 각 위치에서 DFS를 시작한다.
• 반복 루프를 사용하지 않는 경우: 문제에서 탐색을 시작할 특정 위치가 정해져 있고, 그 위치에서 출발하여 목표 지점에 도달할 수 있는지 여부를 확인하는 경우.
  • 단일 DFS호출로 문제를 해결할 수 있다.