[BOJ] #16173 점프왕 쩰리 (Small)

점프왕 쩰리 (Small)

백준 #16173

---

📌 문제

예제 입력

3
1 1 10
1 5 1
2 2 -1

예제 출력

HaruHaru

---

📌 풀이

Logic

• 게임 구역의 크기 N 입력 받기
• board, visited 리스트 생성 <- 백트래킹(BackTracking)
• BFS 함수 구현 (deque)
  • 현재 좌표에서 이동 가능한 좌표를 모두 deque에 추가
  • 이동 가능한 좌표가 도착지(-1)일 경우 종료
  • 불가능한 경우 종료

# 변수명
N : 게임 구역의 크기
board : 게임 구역의 값 리스트
visited : 백트래킹을 위한 리스트
dx, dy : 우/하로만 이동 가능한 문제 조건 반영

dq : 쪨리가 위치한 좌표를 저장하는 deque
nx, ny : 쩰리가 다음 이동할 좌표

Python

import sys
from collections import deque

def bfs(x, y, visited):
    dq = deque()
    dq.append((x, y))
    visited[x][y] = True

    while dq:
        x, y = dq.popleft()

        if board[x][y] == -1:
            return "HaruHaru"

        for j in range(2):
            nx = x + dx[j] * board[x][y]
            ny = y + dy[j] * board[x][y]

            if (0 <= nx < N and 0 <= ny < N and not visited[nx][ny]):
                visited[nx][ny] = True
                dq.append((nx, ny))

    return "Hing"

N = int(sys.stdin.readline())
board = []
visited = [[False] * N for _ in range(N)]

for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    board.append(row)

dx = [1, 0]
dy = [0, 1]

print(bfs(0, 0, visited))

---

✏️ 새로운 내용

너비 우선 탐색(Breadth-first search, BFS)

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

---

📚 회고

💡 BFS

• '자료구조' 수업의 막판에 이론적으로만 알고있던 DFS/BFS를 다루었으며, 백트래킹 이라는 방식에 대해서도 알게 되었다. 그러나 C++을 사용하는 수업이었기에 내가 주로 사용하는 Python으로도 공부를 해보기로 하였다.

💡 종강...!!

• 복학 후 2학년이 드디어 끝났다. 처음으로 많은 전공 수업을 들어보고, 그 과정에서 잊고 살았던 나름의 학구열(?)과 지식들을 얻었다. 3학년으로 넘어가기 전 그동안 배웠던 내용들을 한 번 정리하고 몇몇 프로젝트들도 진행할 예정이지만, 역시나 1일 1백준은 빼먹지 않을 예정이다. 이번에는 대표적인 알고리즘들을(BFS/DFS, DP 등등) 하나당 2주 정도씩 잡고 공부해 볼 생각이다.