바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

Global variable: 실행하는 파이썬 파일 전체 영역에서 사용 가능한 변수

Local variable: 특정 지역 범위에서만 영향을 주고 받을 수 있는 변수

(ex. 특정 함수 내에서 선언한 변수는 return되지 않는 한 함수 밖에서 사용될 수 없다)

#1

a = 1 #Global

def function():
	print(a) 
    # 함수 내에서 별도 변수를 선언하지 않았으므로, Global과 구분되는 Local이 없음
    # 함수 전체에 적용되는 Global 'a'가 적용됨
   
funtion()
print(a)

>> 1 \n 1

여기서 a는 Global variable이다. 

함수 내에서 별도 변수를 선언하지 않았으므로 Local variable은 없다.

함수에서 별도로 변수를 선언하지 않으면 a는 global variable이다.

#2

def function():
	a = 1
    print(a)
    
function()
print(a)

>> 1 \n error

여기서 Global variable은 없다.

함수 내에서만 변수를 선언했으므로 이것은 Local variable, 밖에서 가지고 오면 error 발생.

#3

a = 1 #Global

def function():
	a = 2 #Local
    print(a) #Local
   
function() #Local
print(a) #Global
 
 >> 2 \n 1

Python

global vs nonlocal

global

Global variable: 실행하는 파이썬 파일 전체 영역에서 사용 가능한 변수

함수 내에서 선언한 variable은 기본적으로 해당 함수에서만 사용 가능한 Local이지만, Local을 Global로 전환하는 역할.

때문에 함수 밖에서 선언된 건 global 쓸 필요 없음 (이미 Global인 상태)

#1

a = 1

def function():
	global a #함수 안에서 Local이 아닌 Global을 사용하기로 선언한다
    a = 2 #Global variable 'a'가 2가 된다
    print(a)

function() #Global
print(a) #Global

>> 2 \n 2

이때 global 선언문과 & a에 대한 식을 별도로 지정해야 한다.

#2

def function():
	global a #Local -> Global
    a = 10 #Global
    print(a) #Global

function() #Global
print(a) #Global

>> 10 \n 10

함수 밖에서 변수를 이미 선언하지 않더라도, 함수에서 처음 생성한 변수를 Global variable로 지정할 수 있다.

nonlocal

주로 함수 def 내의 또 다른 함수 def에서 사용됨

nonlocal: lower scope에서의 local variable을 upper scope에서의 local variable로 전환하는 역할

아래 예시에서, function2에서 선언한 a는 기본적으로 function2에서만 사용 가능한 local인데,

그것의 상위 함수인 function1에서 선언한 local으로 전환(연결)하겠다는 의미.

def function():
	a = 1 # function1의 Local
    def function2():
    	nonlocal a
        a = 2
        # nonlocal: function2의 Local -> function1의 Local
        #           function1의 a를 사용하겠어 (연결되겠어)
        # upper scope에서의 variable에 access
        # != Global (whole scope)
        
    function2()
    print(a)
    
>> 2

끝~

https://codingpractices.tistory.com/entry/Python-%EC%A0%84%EC%97%AD-%EB%B3%80%EC%88%98-%EC%A7%80%EC%97%AD-%EB%B3%80%EC%88%98-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%B4%9D-%EC%A0%95%EB%A6%AC-global-nonlocal

⬆️ 위 페이지에 잘 정리되어 있음 !!!

수많은 reportUnboundVariable error

이유를 탐색해보았다.

Reference

https://stackoverflow.com/questions/63388372/why-there-is-an-unbound-variable-error-warning-by-ide-in-this-simple-python-func

➡️ Because range(4) might be something empty (if you overwrite the built-in range), in which case the loop body will never run and a will not get assigned. Which is a problem when it's supposed to get returned.

➡️ Meaning of 'Unbound'

• A symbol that has not been given a value by assignment or in a function call is said to be “unbound.”
• An unbound variable is one that is not within the scope of a quantifier.

➡️ 해결: while문 선언 전 'mid'에 대한 default value를 할당해주었다.

Insertion Sort (삽입 정렬)

: human-like

1. 처음 주어지는 것: 빈 리스트 & 정렬해야 하는 카드들
2. 원리: index 순서대로 읽어가며 이미 정렬된 value들과 크기 비교하여 적절한 위치에 삽입함

• 새로운 빈 리스트를 하나 생성하는 것 대신(메모리 많이 잡아 먹음)
• ⇒ in-place기법 (주어진 표를 변형 + 원본이 훼손됨)

def insertion_sort(list):
	for i in range(i, len(list)):
    	key = list[i]
        j = i-1
        while j >=0 and key < list[j]:
        	list[j+1] = list[j]
        	j -= 1
        list[j+1] = key

1. sorted된 아이템들 중에 현재 Key와의 비교가 이루어질 위치 탐색: O(N) -> binary search 통해 O(logN)
2. shift : O(N)
3. 각 key에 대한 location 최종 삽입: O(1) (이미 1, 2단계로 location이 최종 선택된 상태)
4. 1~3의 단계를 N(=len(list)) 만큼 반복

=> Overall complexity: O(N^2)

관련 문제: 백준 11399 (ATM)

https://www.acmicpc.net/problem/11399

문제 개요

N명, i번 사람이 돈을 인출하는데 P_i분 소요

줄을 서는 순서에 따라 돈을 인출하는 데 각 사람이 인출하는 데 필요한 시간의 합이 달라짐

Input

줄을 서 있는 사람 수 N (ex. 5)

각 사람이 돈을 인출하는 데 걸리는 시간 P (ex. 3 1 4 3 2)

Output

각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값 (ex. 32)

문제 풀이

Pseudo Code

: for문으로 key를 하나씩 지정

각 key의 위치를 while문 통해 탐색

그렇게 필요한 위치를 하나씩 탐색.

비록 시간 복잡도는 n^2

(3, 1, 4, 3, 2)

1 2 3 4 5 => (3, 1, 4, 3, 2) => 39분 (작은 값을 마냥 앞에 배치한다고 개선되지 않음)

2 5 1 4 3 => (1, 2, 3, 3, 4) => 32분

결론: value의 오름차순 소팅! (삽입정렬로 해결)

import sys

for t in range(2):
    if t == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = list(map(int, sys.stdin.readline().split()))

for i in range(1, n):
    key = inputs[i]
    j = i-1
    while j>=0 and key < inputs[j]:
        inputs[j+1] = inputs[j] //swap
        inputs[j] = key //swap
        j -=1 //최종 목적지까지 계속 탐색

answer = [0]
for x in inputs:
    answer.append(x+answer[-1])

print(sum(answer))

https://www.acmicpc.net/problem/11660

👀👉 구간 합 기본 개념 및 전략

Input

표의 크기 N(NxN), 합을 구해야 하는 횟수 M(아주 큼)

둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다

다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어짐

ex. 
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

output

(x1, y1)부터 (x2, y2)까지 합, 총 M개 (각 줄에 하나의 값, M줄)

ex. 

27

6

64

문제 풀이

1. 단순한 구간 합으로 ,,,, 단순 비효율적으로 => 시간 초과

#시간초과

import sys

[N, M] = list(map(int, sys.stdin.readline().split()))
inputs = []
outputs = []
for i in range(N+M):
    if i < N:
        inputs.append(list(map(int, sys.stdin.readline().split())))
    else:
        outputs.append(list(map(int, sys.stdin.readline().split())))

sum_lst = [[0 for _ in range(N)] for _ in range(N)]  # [[0]*N]*N
max_y = max([x[3] for x in outputs])
sums = 0

for y in range(max_y):
    for x in range(N):
        sums += inputs[y][x]
        sum_lst[y][x] = sums

for [a, b, c, d] in outputs:
    if a==c and b==d:
        print(inputs[c-1][d-1])
        continue
    elif a==1 and b==1:
        print(sum_lst[c-1][d-1])
        continue
    elif a>=2 and b==1:
        print(sum_lst[c-1][d-1] - sum_lst[a-2][-1])
        continue
    else:
        f_sum = 0
        for t in range(a-1, c):
            f_sum += sum_lst[t][d-1] - sum_lst[t][b-2]
        print(f_sum)

2. 합 배열과 구간 합의 변용 (중복처리 중요)

문제에 따른 조작적 정의

- 합 배열 :

• 단순히 1번 원소부터 특정 원소까지 다 더한 합이 아니라, 처음부터 직사각형 형태의 합으로 구함
• 점화식의 초항처럼, x=0, y=0일 때의 가장자리 원소를 별도로 구해줌 (base)
• 가장자리 원소(x,y)까지 직사각형 형태의 합 = (x-1까지 직사각형) + (y-1까지 직사각형) - ((x-1, y-1)까지 직사각형)

- 구간 합: 직사각형 형태로 도출될 수 있도록 구함

• (x2,y2)에서 합 배열의 원소 - (x1-1, y2)에서 합 배열의 원소 - (x2, y1-1)에서 합 배열의 원소 + (x1-1, y1-1)에서 합 배열의 원소

import sys

[N, M] = list(map(int, sys.stdin.readline().split()))
inputs = []
outputs = []
for i in range(N+M):
    if i < N:
        inputs.append(list(map(int, sys.stdin.readline().split())))
    else:
        outputs.append(list(map(int, sys.stdin.readline().split())))

sum_lst = [[0 for _ in range(N)] for _ in range(N)]  # [[0]*N]*N
max_y = max([x[3] for x in outputs])

#default setting
sum_lst[0][0] = inputs[0][0]
for x in range(1,N):
    sum_lst[0][x] = sum_lst[0][x-1] + inputs[0][x]
    
for y in range(1,max_y):
    sum_lst[y][0] = sum_lst[y-1][0] + inputs[y][0]


for y in range(1, max_y):
    for x in range(1, N):
        sum_lst[y][x] = sum_lst[y-1][x] + sum_lst[y][x-1] - sum_lst[y-1][x-1] + inputs[y][x]

    
for [x1, y1, x2, y2] in outputs:
    if x1 == x2 and y1==y2:
        print(inputs[x1-1][y1-1])
    elif x1>=2 and y1 >=2:
        print(sum_lst[x2-1][y2-1] - sum_lst[x1-2][y2-1] - sum_lst[x2-1][y1-2] + sum_lst[x1-2][y1-2])
    elif x1==1 and y1>=2:
        print(sum_lst[x2-1][y2-1] - sum_lst[x2-1][y1-2])
    elif x1>=2 and y1==1:
        print(sum_lst[x2-1][y2-1] - sum_lst[x1-2][y2-1])
    else:
        print(sum_lst[x2-1][y2-1])

구간 합 개념

: 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 (가능한 케이스 개수가 극단적으로 많을 경우 특히!)

*핵심: 합 배열 S의 정의

S[i] = A[0] + A[1] + A[2] + .... A[i-1] + A[i]

=> 기존 배열의 일정 범위의 합을 구하는 시간 복잡도: O(N)

=> A[i]~A[j]까지 배열 합: 최악은 i가 0이고 j가 N이므로.

<=> 합 배열을 미리 구해 놓으면 : O(1)로 감소

구현 공식: S[i] = S[i-1](재귀느낌) + A[i](특정 원소)

=> 이것을 기본으로, 문제에 따라 다양한 변용!

구간 합 구현

구현 공식: S[j] - S[i-1]

=> 이것을 기본으로, 문제에 따라 다양한 변용!

https://youtu.be/O514yiWg8YE

https://www.acmicpc.net/problem/17298

1. 문제 개요

1.1 Input

N (ex. 9)

크기가 N인 수열 A (ex. 10 1 2 3 11 4 5 6 12)

1.2 Output

A의 각 원소에 대한 오큰수 배열(*오큰수 NGE(I): 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수)

(ex.  [11,2,3,11,12,5,6,12,-1])

2. 문제 풀이

2.0 귀찮은 백준 입력 세팅: 여러 줄을 입력으로 받는다 (for문 활용 + sys.stdin.readline())

import sys

for y in range(2):
    if y == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = deque(map(int, sys.stdin.readline().split()))

2.1 진짜 단순하게 하나씩: O(n^2)

from collections import deque

answer = deque()
for t in range(n):
    now = inputs.popleft()
    for i in inputs:
        if i > now:
            answer.append(i)
            break
        else:
            continue
    if len(answer) < t+1:
        answer.append(-1)

print(*answer)

Tip: 리스트 내 원소만 출력하고 싶으면, print(*리스트)

2.2 reverse

탐색 문제 풀이 시 input과 output의 관계(경향)을 잘 살피고

• reverse 탐색 / 양방 탐색 등의 방법도 고려해야 함
• 발상의 전환! 반대 방향으로 탐색하면 더 효율적이지 않을까? => 본 문제에서는 여전히 O(n^2)

2.3 O(n^2) => O(n)으로 효율화 필요함! 

• for 문을 한 번만 쓰는 방법,, + 이미 오큰수 구한 원소는 고려 대상에서 제외하는 거,,
• 리스트 내 원소 i는 순차적으로 한 번씩 탐색 (유일한 for문)
• answer = [-1] * n
• stack!! => 오큰수를 찾지 못한 원소의 index를 stack에 저장해두고, 완료된 것은 지움으로써, 당장 필요한 원소만을 추리는 기능
  • stack = [0] 으로 시작 (base case에 대한 사전 처리)
  • while 현재 탐색 중인 i가 stack의 top보다 크면, i는 top의 오큰수가 됨! (이하이면 pass)
  • stack에서 top을 pop (이미 오큰수 구하였으므로 제거) & top의 Index 위치에 해당하는 answer의 value에 오큰수를 저장
  • while 문 끝나면 i가 stack에 append

for y in range(2):
    if y == 0:
        n = int(input())
    else:
        inputs = list(map(int, input().split()))

answer = [-1] * n
stack = [(0)]

for i in range(1, n):
    if inputs[stack[-1]] >= inputs[i]:
        pass
    else:
        while stack and (inputs[stack[-1]] < inputs[i]):
            answer[stack[-1]] = inputs[i]
            stack.pop()
    stack.append((i))
print(*answer)

Tip: stack 저장 대상에 index만 있을 수 있음!

Tip: 반복문에서 pass VS continue

Tip: while stack and 조건: 해당 조건문이 stack이 False인 상태에서 에러 발생!

스택 Stack

1. 마지막에 넣은 것이 - 먼저 나온다
2. stack의 top: 삽입과 삭제가 일어나는 위치
3. s.append(data): top 위치에 새로운 데이터 삽입
4. s.pop(): top 위치의 현재 데이터를 삭제하고 확인
5. s[-1]: top 위치의 현재 데이터를 단순 확인

• DFS: 깊이 우선 탐색
• 백트래킹 종류
• 재귀 알골과 일맥상통

큐 Queue

1. 먼저 들어온 것이 - 먼저 나간다
2. 파이썬에서 deque를 이용하여 큐를 구현 (import collections)
3. stack의 top과 달리, rear(가장 끝)와 front(가장 앞)가 있음
4. s.append(data): rear에 새로운 데이터 삽입
5. s.popleft(): front 부분의 데이터를 삭제하고 확인
6. s[0]: 큐의 맨 앞(front) 데이터 확인

• BFS: 너비 우선 탐색
• 우선순위 큐: 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나옴. ⇒ front에 항상 최댓값 또는 최솟값
  • 힙(heap)을 이용해 구현.

https://youtu.be/JwOFYxirPPU

https://school.programmers.co.kr/learn/courses/30/lessons/43163

문제 개요

rule
1. 한 번에 '한 개의 알파벳'만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

input
- begin 단어
- target 단어
- words 단어의 집합

*각 단어는 알파벳 소문자로만 이루어져 있습니다.
*각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
*words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
*begin과 target은 같지 않습니다.

output
최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지의 값.
*변환할 수 없는 경우에는 0를 return

ex)
input: "hit" / "cog" / ["hot", "dot", "dog", "lot", "log", "cog"]
output: 4
"iii", "jjj", ["iij", "jjj", "iji", "jij"]

BFS + Depth

from collections import deque

def qualify(now, word):
    no = list(now)[:]
    wor = list(word)[:]
    for x in now:
        if x in word:
            if (x in no) and (x in wor):
                no.remove(x)
                wor.remove(x)
    if (len(no)==1) and (len(wor)==1):
        return True
    else:
        return False

def solution(begin, target, words):
    words.append(begin)
    queue = deque()
    queue.append(begin)
    visited = [0]*len(words)

    for x in words:
        if x == begin:
            visited[words.index(x)] = 1
    if target not in words:
        return 0
    while queue:
        now = queue.popleft()
        for idx, word in enumerate(words):
            if qualify(now, word) and (visited[idx]==0):
                queue.append(word)
                visited[idx] = visited[words.index(now)] + 1
            answer = visited[words.index(target)]
            if answer != 0:
                return answer-1

    if answer == 0:
        return 0

• 게임맵 최단거리 로직과 비슷했다
• BFS + Depth
• 가능한 다음 단어 찾는 qualify 함수 추가
• begin의 단어가 words 리스트에 포함될 경우에 대한 별도 처리 필요!!! (처음 에러 이유)
• 하지만 위 코드 역시 더 간결하게 정리될 필요성이 있다. 다시 복습해야지..

https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제 개요

게임 맵 최단거리

*각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리
*캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동
*게임 맵을 벗어난 길& 검은 부분은 갈 수 없습니다
*상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다

input
maps: 게임 맵의 상태
*n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열
*n, m 모두 1이상 100이하 자연수
*n, m모두 1인 경우는 없음.
*0은 벽이 있는 자리, 1은 벽이 없는 자리

내 캐릭터 위치 초깃값: (1,1) == 게임맵 좌측 상단
상대 캐릭터 초깃값: (n,m) == 게임맵 우측 하단

output
상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값
상대 팀 진영에 도착할 수 없을 때는 -1

1) BFS로 구현 + 효율성 최하

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로
    m = len(maps) #세로
    answer = []
    queue = deque()
    queue.append(((1,1), [(1,1)]))
    
    while queue:
        (a,b), route = queue.popleft()
        neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
        for (x,y) in neighbor:
            if (1<=x<=n) and (1<=y<=m) and ((x,y) not in route) and (maps[y-1][x-1] == 1):
                temp = route + [(x,y)]
                if (x==n) and (y==m):
                    answer.append(len(temp))
                else:
                    queue.append(((x,y), temp))        
    if not answer:
        return -1
    else:
        return min(answer)

• 가능한 neighbor을 추려내어 queue에 저장
• 각 노드마다 자신에게 도달하기까지 거쳐야 하는 visited를 temp를 활용하여 모두 저장
• 노드가 도착지점이 되었을 때 answer에 visited의 length를 저장 후 그 가운데 min을 구함
  → 아예 불필요한 절차. (무조건 첫번째 값이 answer가 되기 때문에 바로 return하면 됨)

2) BFS로 구현 + 효율성 하

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로
    m = len(maps) #세로
    answer = 0
    queue = deque()
    queue.append(((1,1), [(1,1)]))
    
    while queue:
        (a,b), route = queue.popleft()
        neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
        for (x,y) in neighbor:
            if (1<=x<=n) and (1<=y<=m) and ((x,y) not in route) and (maps[y-1][x-1] == 1):
                if (x==n) and (y==m):
                    answer = len(route)+1
                    return answer
                else:
                    temp = route + [(x,y)]
                    queue.append(((x,y), temp))
                    
                             
    if not answer:
        return -1

• min 절차 제외하고 answer 나오자마자 바로 return.
• 그렇다고 answer를 visited의 length로 구할 수 없음.
  answer에서 원하는 '방문 노드'와 BFS에서의 'visited'의 기능이 다르기 때문.
  → 각 경로의 vistied가 아니라, 큐 생성 시 제외할 노드를 가리기 위함.
• 여전히 효율성 0점인 이유는?
  1. 각 노드마다 visited를 별도로 구해서 저장하는 게 최악의 비효율.
  2. '노드가 도착지점이 되자마자' 그것이 거쳐 온 노드 개수가 바로 answer가 됨. 이 지점을 활용해야 하는데!
  3. 경로마다 거쳐 온 노드 개수가 다른데 이건 BFS의 Depth를 활용하면 된다!

→ visited 기능을 구현하면서 + BFS의 Depth를 구하는 방법은?

3) BFS로 구현 + Depth 활용 + 효율성 최상 ⭐⭐⭐

from collections import deque

def solution(maps):
    n = len(maps[0]) #가로
    m = len(maps) #세로
    answer = 0
    queue = deque()
    queue.append((1,1))
    
    while queue:
        a,b = queue.popleft()
        neighbor = [(a+1,b), (a, b+1), (a-1, b), (a, b-1)]
        for (x,y) in neighbor:
            if (1<=x<=n) and (1<=y<=m) and (maps[y-1][x-1] == 1):
                    queue.append((x,y))
                    maps[y-1][x-1] = maps[b-1][a-1] + 1
                                 
    if maps[m-1][n-1] == 1:
        return -1
    else:
        return maps[m-1][n-1]

• 명시적인 visited 리스트는 없지만 그 기능을 하는 것이 if maps[y-1][x-1] == 1 조건
  원래 0이면(막혀 있으면) 로직 상 0 초과의 값을 가질 수 없음
  1이면 '뚫려 있지만' '아직 방문된 적 없다'를 의미함
  1 초과 값이면 '방문된 적 있다' & 해당 값은 '나를 방문하기까지 거쳐야 하는 노드 개수'를 의미함.
• BFS의 depth는 maps[y-1][x-1] = maps[b-1][a-1] + 1
  '직전 위치의 값에 +1' 한 값으로 갱신

이와 별개로, BFS 구현 시 주의해야 하는 점. (특히 효율성)

- 혹시 본인의 코드가 방문체크를 큐에서 꺼낼 때 하고있는건 아닌지 확인해보세요.
방문체크를 큐에 넣을 때 해야 효율성이 통과됩니다. 그 이유는 만약 꺼낼 때 방문체크를 하게되면, 하나의 블럭을 꺼내서 통로를 탐색할 때, 이미 큐에 들어있는 블럭을 또 큐에 넣을 수도 있기 때문입니다.

- https://school.programmers.co.kr/questions/23794

https://school.programmers.co.kr/learn/courses/30/lessons/87946

문제 개요

input
k: 현재 피로도 (1이상 5000이하 자연수)
2차원 배열 dungeons: [["최소 필요 피로도", "소모 피로도"], [],...]
*"최소 필요 피로도" >=  "소모 피로도"
*각 값은 1이상 1000이하 자연수
*dungeons 내 원소 중복 가능.
ex) [[80,20],[50,40],[30,10]]

output
유저가 탐험할 수 있는 최대 던전 수
*k값이 0이상일 때까지 반복.

배열의 문제.
어떻게 배열해야 최대한 많은 개수의 던전을 탐험할 수 있을까.

구현 아이디어

BFS (queue 활용)

https://lets-hci-la-ai-withme.tistory.com/51

• 시작정점을 default((k, []))로 고정하고
  BFS 기반으로 - for문 통해 그다음 노드를 선택(단, 조건 충족하는 것만 queue에 인큐)
  
  
• graph는 주어진 2차원 배열 dungeons 사용
• node(첫 시작)을 (k, [])로 지정함.
  • k: (현재 업데이트된) k값
  • [] : visited 역할을 하는 'route'. 어떤 노드를 거쳤는지 노드 인덱스 남기는 리스트. default는 빈 리스트.
• queue 생성 필수: queue = deque() 
• while queue
• 중심 축(매번 업데이트되는 시작 정점)은 queue에서 popleft한 것. (k, route)
  • 그 안에서 for문으로 처리
    • 그다음 탐색할 노드(두 가지 조건 충족 )를 queue에 저장하거나
    • 조건 충족 안 할 경우, max 활용하여 answer 업데이트

from collections import deque

def solution(k, dungeons):
    answer = -1
    queue = deque()
    queue.append((k, []))

    while queue:
        k, route = queue.popleft()
        for i in range(len(dungeons)):
            a, b = dungeons[i]
            if (k>=a) and (i not in route):
                temp = route + [i]
                queue.append(((k-b),temp))
            else:
                answer = max(answer, len(route))

    return answer

좋은 아이디어

복습복습복습!