[백준] 14248 점프 점프 - Python (그래프 탐색)

BAEKJOON Logo

 

 

Contents

 

---

1. 문제 정의 및 예제 해석

(문제 링크: https://www.acmicpc.net/problem/14248)

14248번: 점프 점프

입력과 출력

예제를 보겠습니다. 

5 : 돌이 5개 있는 경우,

1 4 2 2 1 : 각 돌다리 별로 움직일 수 있는 칸의 개수가 주어집니다.

3 : 출발점이 3번째 있는 돌입니다.

방문 가능한 돌들을 살펴보겠습니다. 1 4 2 2 1 중 빨간 색칠된 곳에서 시작합니다.

처음에 왼쪽으로 2칸 가서 1에 도착한 뒤, 오른쪽으로 1칸 가서 4에 도착합니다. 4에서는 갈 곳이 없습니다. 방문한 돌을 초록색으로 표시해보면, 1 4 2 2 1입니다.

한 번에 방문 가능한 돌만 세는 게 아니기 때문에, 다시 가운데 2에서 시작합니다. 이번엔 오른쪽으로 2칸 가서 맨 오른쪽 1에 도착합니다. 이제 왼쪽으로 1칸 가서 4번째 2에 도착합니다. 지금까지 방문한 돌을 초록색으로 표시해보면, 1 4 2 2 11입니다. 즉, 시작점 포함해서 모든 돌 5개를 다 방문했습니다. 그에 따라 5를 출력합니다.

 

2. 전체 코드

import sys
input = sys.stdin.readline # input함수 빠르게
sys.setrecursionlimit(10**6) # dfs 재귀호출 충분히늘려두기
n=int(input()) # 돌 개수
b=list(map(int, input().split())) # 각 돌다리별로 움직일 수 있는 칸의 개수
s=int(input()) # 출발점
cnt=1 # 방문한 돌 개수. 출발점 1개부터
v=[0]*n # 방문한 돌 표시
def dfs(x):
    global cnt
    for nx in (x+b[x], x-b[x]):
        if 0<=nx<n and v[nx]==0:
            cnt+=1;v[nx]=1
            dfs(nx)
dfs(s-1)
print(cnt)

 

3. 코드 해설

1) 입력

import sys
input = sys.stdin.readline # input함수 빠르게
sys.setrecursionlimit(10**6) # dfs 재귀호출 충분히늘려두기
n=int(input()) # 돌 개수
b=list(map(int, input().split())) # 각 돌다리별로 움직일 수 있는 칸의 개수
s=int(input()) # 출발점

input = sys.stdin.readline은 input함수를 sys.stdin.readline으로 대체하는 것입니다. 이유는 파이썬의 input() 함수보다 sys.stdin.readline 함수가 훨씬 빠르게 표준 입력을 받을 수 있기 때문입니다. 

다음으로, sys.setrecursionlimit(10**6)을 합니다. 이는 재귀 함수 호출할 때, 재귀 호출의 최대치를 10**6까지 설정하는 것입니다. 아래에서 재귀 함수를 정의하고 사용하기 때문에 충분하게 호출 횟수를 늘려 둡니다.

n은 돌 개수를 입력받고, b는 돌다리 별로 움직일 수 있는 칸 개수를 리스트로 받습니다. s는 출발점 위치입니다.

 

2) 핵심 알고리즘

cnt=1 # 방문한 돌 개수. 출발점 1개부터
v=[0]*n # 방문한 돌 표시
def dfs(x):
    global cnt # cnt 전역 변수 설정
    for nx in (x+b[x], x-b[x]):
        if 0<=nx<n and v[nx]==0:
            cnt+=1;v[nx]=1
            dfs(nx)

cnt=1은 출발점도 방문한 돌이기 때문에, 1로 시작합니다. v=[0]*n에서 n이 3이라면 v는 [0, 0, 0]으로 만들어집니다. 방문한 돌을 표시하기 위한 리스트입니다. 다음으로 깊이 우선 탐색 기반 함수를 dfs라는 이름으로 만듭니다. 함수 밖에서 정의한 cnt를 가져다 쓰기 위해, 함수 내부에서 global cnt라고 해줍니다. dfs는 입력으로 시작 돌의 인덱스(x)를 받습니다. x돌이 몇 칸 갈 수 있는지 만큼은 b[x]에 쓰여있습니다. x+b[x]는 x에서 오른쪽으로 b[x]만큼 가는 것을 의미하고, x-b[x]는 왼쪽으로 b[x]만큼 가는 것을 의미합니다. 이렇게 두 번을 nx(next) 변수에 넣어서, 조건문을 통해 0<=nx<n(다음 방문할 돌이, 돌의 인덱스에 포함되는지 여부)와 v[nx]==0 (방문 안 한 돌이 맞는지 여부)를 판단해서 방문하지 않았고, 돌다리 인덱스에 포함된다면 cnt+=1;v[nx]=1 방문한 돌 개수 cnt에 1을 더해주고, 방문했다고 v리스트에 표시해줍니다. 그리고 dfs(nx)를 호출해서 nx돌을 기반으로 다음 방문할 돌을 탐색합니다.

 

* 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

DFS와 BFS

3) 출력

dfs(s-1)
print(cnt)

위에서 정의한 dfs함수에 s-1을 넣어줍니다. s-1인 이유는 인덱스는 0부터 시작이기 때문입니다. 예를 들어, s가 3인 경우 3번째 돌의 인덱스는 2입니다. 그렇게 dfs를 모두 수행하면, 전역변수화된 cnt에 방문한 돌의 개수가 저장되어 있으니, cnt를 출력하면 정답입니다.

 

4. 느낀점

전형적인 그래프 탐색 문제였습니다. 오랜만에 풀어서 어떻게 풀지 감이 잡히지 않아서, 다른 사람의 풀이를 읽어본 뒤에 풀어보았습니다. 친척 동생 이름이 영우인데, 군대 간 영우가 떠오르는 알고리즘 문제였습니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

Reference)
1. DFS와 BFS: https://velog.io/@xmun74/%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS