[BOJ][Python] 16173번 - 점프왕 쩰리 (Small)[DFS/BFS - 실버 5티어]

알고리즘 태그

[DFS/DFS 탐색]

태그 설명

BFS - 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
DFS - 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 해당 노드의 끝까지 탐색하고 목표 노드에 도달하면 멈추고 아니면 그 다음 노드의 자식노드들을 또 끝까지 탐색하는 방식의 탐색법

 

DFS, BFS 비교

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

문제

백준 문제 - 점프왕 쩰리

링크: 점프왕 쩰리

문제설명

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

예제 입력

3
1 1 10
1 5 1
2 2 -1

예제 출력 

HaruHaru

쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로,  (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다.

예제 입력 

3
2 2 1
2 2 2
1 2 -1

예제 출력 

Hing

 

탐색 문제의 경우에는 DFS 혹은 BFS를 사용하여 풀 수 있다. 다만 DFS의 경우에는 수행시간이 오래 걸릴 수 있다는 점만 인지하고 있으면 된다. 그 이유는 DFS의 경우 첫 노드의 자식노드까지 탐색이 완료될 때까지 다음 노드로 진행하지 않기 때문에 첫 노드에 대박이 나는게 아니라면 시간이 오래걸린다..

일단 나는 bfs를 통해서 문제를 풀었다. BFS는 Queue를 이용해서 푸는것이 핵심이다.

📃 소스코드 및 설명

from collections import deque
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]

# 방문 유무 확인
visited = [[False]*3 for _ in range(N)]

# 오른쪽만 가능
dx = [1,0]

# 아래만 가능
dy = [0,1]

def bfs(x, y):
  
  q = deque()
  q.append([x,y])
  

  while q:
    x, y = q.popleft()
    # 쪨리가 현재 밟고 있는 칸의 숫자를 인출해준다.
    step = graph[x][y]

    # 끝점이 -1이므로 -1로 도달하면 성공!
    if graph[x][y] == -1:
      return True
    for move in range(2):
      # 쩰리가 현재 밟고 있는 숫자를 인출하고 이동수에 곱해서 이동해준다. 
      nx = x+dx[move]*step
      ny = y+dy[move]*step
      
       # 주어진 범위를 벗어나는 경우 무시
  	   # x, y의 범위가 0,0보다 작아지거나, 주어진 matrix의 크기를 초과하는 경우
      if nx < 0 or nx >= N or ny < 0 or ny >= N:
        continue

      # 방문하지 않았을경우만
      if not visited[nx][ny]:
      	# 방문으로 수정해준다.
        visited[nx][ny] = True
        # 아직 우리가 찾는 조건(graph[x][y] == -1)이 아니므로 q에 담아주고 다시 반복해준다.
        q.append([nx, ny])  
        
if bfs(0,0):
    print('HaruHaru')
else:
    print('Hing')

 

같은 문제를 dfs를 통해서 풀면 아래와 같이 풀 수 있다.

import sys
input=sys.stdin.readline


def dfs(x,y) :
    #영역을 벗어났거나 이미 방문을 했다면 return
    if x<=-1 or x>=N or y<=-1 or y>=N or visit[x][y]==1:
        return
    
    #방문한 곳의 이동 칸 수가 -1이라면 방문처리를 해주고 return 한다. 
    if graph[x][y] == -1 :
        visit[x][y] = 1
        return

    #방문했다고 표시해준다.
    visit[x][y]=1

    #상,하,좌,우를 요소 수만큼 점프하여 방문한다.
    dfs(x+graph[x][y],y)
    dfs(x,y+graph[x][y])



#게임 구역의 크기 N을 입력받는다.
N=int(input())

#게임판의 구역을 입력받는다. 2차원 리스트
graph=[list(map(int,input().split())) for _ in range(N)]

#방문여부를 저장할 visit 2차원 리스트를 만든다.
visit=[[0]*N for _ in range(N)]

#출발은 0,0에서 하므로 dfs(0,0)을 호출한다.
dfs(0,0)

#결과 출력
if visit[-1][-1] == 1 :
    print('HaruHaru')
else :
    print('Hing')