BOJ 16173번 - 점프왕 쩰리

BFS와 DFS에 대하여 공부하고 있다.

 

그 중 BFS란, 너비 우선 탐색을 의미한다. 가까운 노드들부터 우선적으로 탐색한다는 것이다.

 

이에 해당 개념을 잡기 위해, 수 차례 의미를 생각하며 코드를 쳐보았지만 아직 부족함을 느꼈다.

 

이에 BFS 개념을 적용해보고자, 백준 OJ에서 다음과 같은 문제를 찾아 풀어보았다.

 

문제

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

입력

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

출력

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

 

2차원 배열을 사용해야만 풀 수 있었으므로, 문제의 조건에 맞게 배열을 먼저 생성했다.

하지만 거기까지였다.

막상 bfs 함수를 써놓고 보니, 이것을 어찌 적용해야할 지 막막했다.

결국 다른 블로그들을 찾아가며, 다른 사람들이 어떠한 과정과 어떠한 풀이로 푸는 지를 찾는 수밖에 없었다.

 

from collections import deque

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))

visited = [[False] * n for _ in range(n)]

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

def bfs(x, y, visited):
    queue = deque()
    queue.append((x,y))
    visited[x][y] = True
    while queue:
        x,y = queue.popleft()
        if graph[x][y] == -1:
            return "HaruHaru"
        for i in range(2):
            nx = x + dx[i] * graph[x][y]
            ny = y + dy[i] * graph[x][y]
            print(f'좌표:{(x,y)} 이동:{(nx,ny)}')
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if visited[nx][ny]:
                continue
            if not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx,ny))
                print("first visit")
        print('-----')
    return "Hing"
    
print(bfs(0,0,visited))

 

while 문 안에서, 분기가 일어나거나 계산이 일어나는 부분에 대하여 출력을 통해 어떤 일이 일어나는지 알 수 있도록 보았다.

 

3
1 1 10
1 5 1
2 2 -1
좌표:(0, 0) 이동:(1, 0)
not visited
좌표:(0, 0) 이동:(0, 1)
not visited
-----
좌표:(1, 0) 이동:(2, 0)
not visited
좌표:(1, 0) 이동:(1, 1)
not visited
-----
좌표:(0, 1) 이동:(1, 1)
좌표:(0, 1) 이동:(0, 2)
not visited
-----
좌표:(2, 0) 이동:(4, 0)
좌표:(2, 0) 이동:(2, 2)
not visited
-----
좌표:(1, 1) 이동:(6, 1)
좌표:(1, 1) 이동:(1, 6)
-----
좌표:(0, 2) 이동:(10, 2)
좌표:(0, 2) 이동:(0, 12)
-----
HaruHaru

그 결과, 비로소 함수 내부에서 어떠한 일이 일어나는 지 파악할 수 있었다.

그래프의 범위를 초과하지 않을 때에만 해당 위치로 이동을 하고,

이미 방문한 곳이면 그냥 넘어간다.

 

이런 방식이면 최종 도착지인 -1에 도착할 수 있는지 없는지를 알 수 있지만,

더불어 어디에 갈 수 없는지도 파악할 수 있다.

 

해당 방법 내에서 사용한 dx, dy는 이동 방향을 나타내는 것인데, 만약 위, 왼쪽으로도 이동할 수 있었다면

(1,0), (0,1) 뿐만 아니라 (-1,0), (0,-1)가 추가되었거나,

nx = x - dx[0]~ 과 같은 식으로 뺄셈이 들어가는 연산이 추가되었을 것이다.

 

이렇게 dx, dy를 지정하여 좌표 상에서의 이동을 나타내는 문제는 이미 전에 다른 구현 문제를 통해 풀어본 바가 있었는데,

그 점을 해당 문제에 적용하여 풀지 못했다는 것이 아쉬웠다.

 

사실 크게 어려운 문제가 아니었음에도, 그냥 혼자 어렵게 생각하여 접근 방식 자체를 파악하지 못한 것이 아니었나 싶다.