문제

입력

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

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

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

출력

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

입력 예시 1

3
1 1 10
1 5 1
2 2 -1

출력 예시 1

HaruHaru

입력 예시 2

3
2 2 1
2 2 2
1 2 -1

출력 예시 2

Hing

문제 이해

이 문제는 다른 DFS문제에 비해서 DFS 느낌이 덜 났다. 그리고 이 문제가 나는 처음에 지그제그로 움직일 수 있을 줄 알아서 더 어렵게 생각했었다. 그런데 알고보니 한번 움직일 때는 한 방향으로만 움직일 수 있다.

보통의 DFS 문제와 다른 것은(현재 나는 DFS 한놈만 패고 있기에 BFS는 고려하지 않음) 각 칸에 있는 숫자만큼 오른쪽으로 또는 아랫쪽으로 움직일 수 있다는 것이다.

틀린 코드

# 백준 16173번 점프왕 쩰리(Small)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향벡터 동-남 순
dx = [1, 0]
dy = [0, 1]

def DFS(y, x):
    global game_map, answer

    if y == (N-1) and x == (N-1):
        answer = "HaruHaru"
        return

    # 점프를 지그제그로 하지 못함 한방향으로만 가능
    # 만약 점프가 지그제그로 됐으면 훨씬 까다로웠을 거임
    for i in range(2):
        new_x = x + dx[i] * game_map[y][x]
        new_y = y + dy[i] * game_map[y][x]
        if 0 <= new_x < N and 0 <= new_y < N:
            DFS(new_y, new_x)
        

# 0. 입력 및 초기화
N = int(input())
game_map = []
answer = "Hing"

# 1. 게임맵 정보 입력
for _ in range(N):
    game_map.append(list(map(int, input().split())))

# 2. DFS호출
DFS(0, 0) # y, x

# 3. 출력
print(answer)

틀린 이유 - visited를 사용하지 않아서

어차피 경로가 중복되지 않을거라고 생각해서 visited를 추가하지 않고 그냥 DFS만 돌렸더니 메모리 초과가 났다. 알고보니 하는 한줄기의 DFS호출만 생각했다. 당연히 한줄기의 DFS라면 움직이는게 오른쪽, 아랫쪽만 가니까 안겹치겠지라고 생각했다. 하지만 이문제에서는 여러개의 DFS 줄기가 사용된다. 모든 DFS가 그렇듯이.

예를 들면, 3*3 맵이라고 가정했을때, 그리고 (0, 0)의 값이 1일때, 아래로 1칸 가서 시작한 것과 오른쪽으로 1칸 가서 시작한 두 경우는 다른 DFS이고 다른 줄기이다. 계속 DFS가 재호출 되다가 결국 둘다 (1,1)에서 만나게 된다면 한번 지나간 자리이고 이 자리에서 (2, 2)로 도달할 수 없다는 걸 아는 상태인데 굳이 또 한번 (1, 1)을 가는 것은 메모리 낭비고 시간 낭비이다. 난 visited를 사용하지 않았기 때문에 이런 경우도 모두 여러번씩 재호출한 거고 그래서 메모리 오류가 났다.

코드 및 설명

# 백준 16173번 점프왕 쩰리(Small)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 방향벡터 동-남 순
dx = [1, 0]
dy = [0, 1]

def DFS(y, x):
    global game_map, answer, visited

    visited[y][x] = True
    
    if y == (N-1) and x == (N-1):
        answer = "HaruHaru"
        return

    # 점프를 지그제그로 하지 못함 한방향으로만 가능
    # 만약 점프가 지그제그로 됐으면 훨씬 까다로웠을 거임
    for i in range(2):
        new_x = x + dx[i] * game_map[y][x]
        new_y = y + dy[i] * game_map[y][x]
        if 0 <= new_x < N and 0 <= new_y < N and not visited[new_y][new_x]:
            DFS(new_y, new_x)
        

# 0. 입력 및 초기화
N = int(input())
game_map = []
answer = "Hing"
visited = [[False] * N for _ in range(N)]

# 1. 게임맵 정보 입력
for _ in range(N):
    game_map.append(list(map(int, input().split())))

# 2. DFS호출
DFS(0, 0) # y, x

# 3. 출력
print(answer)

기본적인 DFS문제보다는 조금 헷갈렸다.

지금까지 DFS강의를 듣고 문제를 풀면서 DFS감을 익혔다. 이 문제가 강의에 있는 마지막 문제이다. 이로써 강의의 컨텐츠는 모두 소화했다. 바로 더 높은 난이도의 DFS를 풀지, 다른 알고리즘을 공부를 할지 고민해봐야겠다.

내가 들었던 DFS 강좌
https://www.inflearn.com/course/lecture?courseSlug=python-%EB%AC%B8%EA%B3%BC%EC%83%9D-%EC%9D%B4%ED%95%B4%ED%95%98%EB%8A%94-dfs-%EC%9E%85%EB%AC%B8&unitId=178069&subtitleLanguage=ko

사실 강의가 좀 날먹같기도 하다. 왜냐하면 너무 비슷한 문제도 많이 다루었기 때문에. 그게 장점이면서 단점이다. 초보자는 감을 잡기에 좋긴하지만, 감을 잡으니까 실제로 정말 도움이 된 강의는 몇강 되지 않는다. 뭐 아무튼 일단 DFS 감을 잡는데는 너무 도움이 됐다.