[백준] 1326 폴짝폴짝 파이썬 풀이

1326번: 폴짝폴짝

[문제]

 

---

[코드]

from collections import deque

def bfs(start, finish, stone, n):
	q = deque()
    q.append(start - 1)
    visited = [-1] * n 
    visited[start-1] = 0
    
    while q:
    	node = q.popleft()
        for i in range(n):
        	if (i-node) % stone[node] == 0 and visited[i] == -1:
            q.append(i)
            visited[i] = visited[node] + 1
            if i == finish -1:
            	return visited[i]
                
    return -1
    
n = int(input())
stone = list(map(int, input().split()))
start, finish = map(int, input().split())
print(bfs(start, finish, stone, n))

---

[해설]

 

어렵다... 정확히 말하자면 귀찮은 문제 - 고려할 사항이 많다

 

bfs (너비 우선 탐색) 문제이다

따라서 기본적인 너비 우선 탐색의 로직을 따라간다 [너비 우선 탐색에 대한 자세한 내용은 나중에 따로 다뤄보겠다]

 

 

이번 문제 해결의 핵심 bfs()함수 이다

def bfs(start, finish, stone, n):
    q = deque()
    q.append(start - 1)
    visited = [-1] * n
    visited[start-1] = 0

    while q :
        node = q.popleft()
        for i in range(n):
            if (i-node) % stone[node] == 0 and visited[i] == -1:
                q.append(i)
                visited[i] = visited[node] + 1
                if i == finish-1:
                    return visited[i]
    return -1

우선 deque를 만들어 주고 (데크 - 선입선출  - 큐)

start 위치를 추가해준다

그리고 방문 여부를 확인해주는 visited를 -1로 돌의 갯수 만큼 채워준다 

 

(방문 여부는 걸리는 횟수를 저장해주는 DP이다)

 ex) n=9 , visited = [-1, -1, -1, -1 ,-1 , -1, -1, -1, -1]

그런다음 시작점을 방문 처리 해준다

 

다음 은 q가 빌때까지 while 문을 반복하여 계산해준다

 먼저 node변수를 만들어서 q의 가장 왼쪽 (선입선출)을 꺼내온다 (꺼내 온다는 것은 q에서 값이 사라진다)

 그리고 돌의 크기 만큼 for 문을 적용하여

    while q :
        node = q.popleft()
        for i in range(n):
            if (i-node) % stone[node] == 0 and visited[i] == -1:
                q.append(i)
                visited[i] = visited[node] + 1
                if i == finish-1:
                    return visited[i]
    return -1

(1) (i-node) % stone[node] == 0 

 

 stone[node]에서 갈 수 있는 위치 판단

즉, stone[node]에서 i 까지의 거리가 stone[node]의 값의 배수인지를 판단

 ex) 처음 시작점 = node라면

시작점에서 i까지의 거리를 측정 (i-node)

이때 거리가 시작점 돌의 값의 배수인지 측정

 

 

(2) visited[i] == -1 

방문 여부를 확인, 최종 걸리는 횟수저장

 

 

 

그리고 이 조건들을 모두 만족한다면 q에 i를 추가해주고

방문의 횟수를 visited[node]의 값에 1을 더해서 변환시켜준다

 

그리고 만약 i 가 종료지점과 값이 같다면 visited[i]의 값을 return하고

 

while 문이 다 돌때까지 리턴 값이 없다면 -1를 리턴한다

 

 

 

ex) 예제 1 적용

5 - stone 갯수
1 2 2 1 2 - stone의 각 값

1 5 - 시작과 출발

 

**시작**

q.append(0) >> q = [0]visited = [-1] * n  >> visited = [-1 , -1, -1, -1, -1]visitied[start -1] = 0 >> visitied = [0, -1, -1, -1, -1]

 

while q:

   node = q.popleft() >> node = 0

   for i in range(n):

         1) i == 0

               i- node =  0  >> (i-node) % 1 == 0

               but visited[0] = 0

         pass

 

         2) i == 1

               i- node =  1  >> (i-node) % 1 == 0

              visited[1] = -1

              q = [1]

              visited = [0 , 1, -1, -1, -1]

 

         3) i == 2

              i- node =  2  >> (i-node) % 1 == 0

             visited[2] = -1

              q = [1, 2]

              visited = [0, 1, 2,  -1, -1]

              

        4) i== 3

            i- node =  3  >> (i-node) % 1 == 0

            visited[3] = -1

            q = [1, 2, 3]

            visited = [0, 1, 2,  3, -1]

         

        5)i==4

            i- node =  4  >> (i-node) % 1 == 0

            visited[4] = -1

            q = [1, 2, 3, 4]

            visited = [0, 1, 2,  3, 4]

 

           and i == finish -1

        retrun == 4