미정

백준에서 처음으로 DFS와 BFS 문제를 접했는데 해설을 자세하게 해볼려고 한다.

문제 링크

1260번: DFS와 BFS

해설

N,M,V = map(int,input().split())

#행렬 만들기
graph = [[0]*(N+1) for _ in range(N+1)]
for i in range (M):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

#방문 리스트 행렬
visited1 = [0]*(N+1)
visited2 = visited1.copy()

#dfs 함수 만들기
def dfs(V):
    visited1[V] = 1 #방문처리
    print(V, end=' ')
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:
            dfs(i)

#bfs 함수 만들기
def bfs(V):
    queue = [V]
    visited2[V] = 1 #방문처리
    while queue:
        V = queue.pop(0) #방문 노드 제거
        print(V, end = ' ')
        for i in range(1, N+1):
            if(visited2[i] == 0 and graph[V][i] == 1):
                queue.append(i)
                visited2[i] = 1 # 방문처리

dfs(V)
print()
bfs(V)

1. 행렬 만들기

행렬을 만들 때 자주 사용되는 리스트 컴프리헨션 문법을 사용한다.

graph = [[0]*(N+1) for _ in range(N+1)]
for i in range (M):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

[[0]*(N+1)] 은 N이 3이라면 [[0] * (4)] 이므로 => [[0,0,0,0]]을 출력한다. 
리스트 컴프리헨션을 써주면 [[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]행렬이 완성된다.

graph =   0 1 2 3 행
	0 0 0 0 0
        1 0 0 0 0
        2 0 0 0 0
        3 0 0 0 0
        열
        
정점의 개수만큼의 행렬을 만들었다면,
이제는 정점 간의 연결을 행렬에 표시해 주어야한다.
만약 '1 2'가 입력된다면 정점1과 정점2가 연결되어있다는 뜻이므로 0을 1로 바꿔준다.

graph[1][2] = graph[2][1] = 1

graph =   0 1 2 3 행
	0 0 0 0 0
	1 0 0 1 0
	2 0 1 0 0
	3 0 0 0 0
	열

2. 방문 리스트 만들기

BFS와 DFS는 스택과 큐를 사용한다. 이때 스택과 큐에 한번 들어갔던 노드는 다시 들어가지 못한다.

즉, 이 노드가 스택과 큐에 들어갔던 적이 있는지 확인할 필요가 있다. 이를 표현하기 위해 정점의 수만큼의 방문 리스트를 만들겠다.

visited1 = [0]*(N+1)
visited2 = visited1.copy()

N이 3이라면, visited1 = [0,0,0,0]
만약 1번 노드가 스택에 들어간 적이 있다면 visited = [0,1,0,0] 이 될 것이다.

3. DFS 함수 만들기 - 재귀 사용

def dfs(V):
    visited1[V] = 1 #방문처리
    print(V, end=' ')
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:
            dfs(i)
            
탐색을 시작하는 번호 V부터 탐색을 시작한다.
먼저 V노드가 시작이므로 V를 방문 처리한다. 
예를들어 V=1이라면 위에서 만들어놓은 방문 리스트에서 visited1[1] = 1 로 방문처리하는 것이다.
그러면 visited1 = [0,1,0,0]이 될 것이다.
이는 1번 노드가 스택에 들어간적이 있다는 기록인 것이다.

1번 노드가 방문했으므로 1번 노드를 출력한다.
print(V, end=' ')

이 후 for문을 돌려서 if graph[V][i] == 1로
graph[1][1], graph[1][2], graph[1][3]을 확인해 줄 것이다.
이는 1과 연결된 노드를 찾는 것이다. (위에서 행렬로 연결된 노드들을 1로 표시해두었으므로)

만약 1과 2가 연결돼있다면 graph[1][2] == 1에 True가 될 것이다.
여기서 and visited1[i] == 0으로 2번 노드가 스택에 들어갔던 적이 있는지 확인해주어야 한다.
만약 2번 노드가 스택에 들어간적이 있다면 만들어놓은 방문리스트에서 1값으로 변경되었을 것이다.

즉, 1과 연결된 노드 중 방문기록이 없는 노드를 찾는 코드이다.
if graph[V][i] == 1 and visited1[i] == 0:

1과 연결된 노드 중 방문기록이 없는 노드가 있다면
dfs(i)로 재귀함수를 돌린다.

dfs(2)는 다시 위의 과정을 돌려서 2를 방문처리하고, 2와 연결된 노드를 찾는다.
이렇게 계속 연결된 노드들을 찾아 '깊이우선탐색'을 진행하는 것이다.  

4. BFS 함수 만들기

def bfs(V):
    queue = [V]
    visited2[V] = 1 #방문처리
    while queue:
        V = queue.pop(0) #방문 노드 제거
        print(V, end = ' ')
        for i in range(1, N+1):
            if(graph[V][i] == 1 and visited2[i] == 0):
                queue.append(i)
                visited2[i] = 1 # 방문처리
      
      
bfs는 queue를 이용한다.
탐색 시작 노드 V가 주어진다면
queue = [V] 로 큐에 탐색 노드를 먼저 넣는다.
이 후, 위에서 만들어놓은 방문리스트 visited2[V] = 1로 방문 처리해준다.
V가 1이라면 visited2 = [0,1,0,0]이 될 것이다.
dfs와 같은 원리이다.

이제 while queue: 로 queue에 값이 없을때까지(탐색이 끝날때까지) 반복할 것이다.
먼저 queue.pop(0)을 해준다. 이 코드는 queue에서 0번째 요소를 돌려주고 삭제하라는 것이다.
queue는 선입선출 구조이므로 가장 먼저들어온 0번째 요소부터 빼는 것이다.
그리고 삭제한 요소를 V변수로 돌려받겠다.
위에서 V를 1로 가정했을 때 queue = [1], visited[2] = [0,1,0,0]인 상태이고
여기서 V = queue.pop(0)을 해주면 queue = []이 되고, V = 1이 될 것이다.
1을 뺐으니 1을 출력한다. print(V, end = ' ')

이 후 for문으로 연결된 노드들을 탐색해줄 것이다.
원리는 위에 설명한 dfs와 같다.
V와 연결되고, 방문한 적이 없는 노드가 있다면
큐에 넣어줄 것이다.


bfs과정을 나열해보겠다.
V = 1 // 1번 노드부터 탐색시작
queue = [1] // 방문 노드 저장
visited2[1] = 1 // visited2 = [0,1,0,0]

while문 들어가서,
queue = []
V = 1 // 1출력
for문 들어가서,
노드 1과 2가 연결되고, 노드 2가 방문된적이 없다면
graph[1][2] ==1 and visited2[2] == 0에 해당하므로
queue = [2]
visited2[2] = 1로 방문처리

노드 1과 3이 연결되고, 노드 3이 방문된적이 없다면
queue = [2,3]
visited2[3] = 1로 방문처리
모든 연결 노드 확인 후 for문 반복 끝

queue에 값이 있으므로
while문 탈출 안하고 다시 반복
V = 2 // 2출력
queue = [3]
graph[2][1] == 1 and visited2[2] ==0에 해당하지 않으므로 큐에 다시 넣지 못한다.(2는 1과 연결돼있지만, 1은 이미 큐에 들어간 기록이 있다.)
graph[2][3] == 1 and visited2[2] ==0 역시 마찬가지로 방문기록이 있으므로 false

이 경우 아무것도 추가되지 않고 for문을 빠져나간다.
queue = [3]으로 아직 값이 있으므로 while문 다시 반복
V = 3 
queue = []

5. BFS 함수 더 이해하기

queue는 pop(0)을 통해 먼저 들어온 요소를 뺀다.
선입선출인 큐가 너비우선탐색을 하게하는 핵심이다.

아래와 같이 연결된 노드가 있다고 가정해보자.
(1-2,1-3,1-4,3-5,4-6,6-7 연결)

1 - 2 
  - 3 - 5 
  - 4 - 6 - 7
  
  
queue에는 시작 노드를 먼저 담고 시작한다.
queue = [1]로 시작해서 1을 뺀 후 출력한다.
// queue = []
// 출력: 1
이 후 1과 연결된 2,3,4 가 queue에 담길 것이다.

// queue = [2,3,4]
0 번째 요소 (가장 먼저들어온) 2번 노드를 빼고 출력한다.
// 출력: 1 2
2와 연결된 노드를 확인한다.
2와 연결된 노드가 없다면 추가되지 않는다.

// queue = [3,4]에서
0 번째 요소 3번 노드를 빼고 출력한다.
// 출력: 1 2 3
3과 연결된 노드를 확인한다.
3과 연결된 5가 queue에 담길 것이다.

// queue = [4,5]
0 번째 요소 4번 노드를 빼고 출력한다.
// 출력: 1 2 3 4
4와 연결된 노드를 확인한다.
4와 연결된 6이 queue에 담길 것이다.

// queue = [5,6]
0 번째 요소 5번 노드를 빼고 출력한다.
// 출력: 1 2 3 4 5
5와 연결된 노드를 확인한다.
5와 연결된 노드가 없다면 추가되지 않는다.

// queue = [6]
0 번째 요소 6번 노드를 빼고 출력한다.
// 출력: 1 2 3 4 5 6
6과 연결된 노드를 확인한다.
6과 연결된 7이 queue에 담길 것이다.

// queue = [7]
0 번째 요소 7번 노드를 빼고 출력한다.
// 출력: 1 2 3 4 5 6 7
7과 연결된 노드를 확인한다.
7과 연결된 노드가 없다면 추가되지 않는다.

queue = [] 빈 문자열이므로 while 반복문을 달출한다.

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

풀이 

이런 문제는, 문제에서 규칙을 찾을 수 있는지 확인해야 한다.
일단 대각선의 값이 눈에 띈다. 대각선의 원소들은 1, 2, 3, 4, ...의 순서로 배열되어 있다.
이 대각선의 값을 기준으로, 왼쪽 직선과 위쪽 직선은 같은 값을 가지고 있다.
위와 아래는 인덱스 값이 약 n만큼 차이가 나고, 대각선의 한 원소로부터 왼쪽의 원소들은 인덱스 값이 1씩 줄어든다.
여기서 i // n과 i % n를 적절히 활용하면 풀 수 있을 것이라는 것을 직감적으로 느낄 수 있다.
정확한 규칙을 찾기 위해 몇 가지의 인덱스 값들을 예시를 들어 비교해보면,

예시 1번을 보면  n=3일때 배열을 열이 1인 행렬로 그려보면

0 (0,0) 1 (0,1) 2 (0,2) 3 (1,0) 4 (1,1) 5 (1,2) 6 (2,0) 7 (2,1) 8 (2,2)
이런식으로 볼수 있다.
만약 내가 구하고자 하는 같이 index 8번이라면, 8 ( 8//3, 8% 3)=( 몫, 나머지)로 확인할 수 있다.

그리고 몫과 나머지중 가장 큰값에 따라서 숫자가 들어간다!

즉, index = 8, n = 4 이라면

(i // n, i % n) → (2, 0) → 3

이거에 +1을 한것이 답이 된다 !

def solution(n, left, right):
    answer = []
    for i in range(left, right+1):
        a = i//n
        b = i % n
        if a < b:
            a,b = b,a
        answer.append(a+1)
        
    return answer

문제 설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

종류 이름

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

입출력 예

clothes return

입출력 예 설명

예제 #1

headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat 2. blue_sunglasses 3. green_turban 4. yellow_hat + blue_sunglasses 5. green_turban + blue_sunglasses

예제 #2

face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask 2. blue_sunglasses 3. smoky_makeup

문제 풀이

def solution(clothes):
    answer = 1
    dic = {}
    for i in clothes:
        if i[1] in dic:
            dic[i[1]] += 1
        else:
            dic[i[1]] = 1
    for i in dic.keys():
        answer *= dic[i] + 1
    return answer - 1

1. key, value 로 분류하면 된다. 그래서 딕셔너리를 사용했다.
2. 빈 딕셔너리 dic {} 을 설정한다.
3. [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] 이 입력값일 때

• i = ["yellow_hat", "headgear"]
• i[1] 은 headgear,
  dic[i[1]] ⇒ i[1]인 headgear를 Key로 하여 Value에 1을 넣으라는 뜻이다.
  즉, dic = {"headgear": 1}
• 위의 예시에서 총 경우의 수는 6가지이다.
  1. yellow_hat을 입고, blue_sunglasses를 입음
  2. green_turban을 입고, blue_sunglasses를 입음
  3. yellow_hat을 입고, 아무 것도 입지 않음
  4. green_turban을 입고, 아무 것도 입지 않음
  5. 아무 것도 입지 않고, blue_sunglasses를 입음
  6. 아무 것도 입지 않음 (아무 것도 입지 않는 경우)
• headgear 종류는 2개의 아이템(yellow_hat과 green_turban)이 있다.
  이 경우, headgear를 입는 경우의 수는 3가지이다.
  • yellow_hat을 입거나, green_turban을 입거나, 아무 것도 입지 않는 경우.
• eyewear 종류는 1개의 아이템(blue_sunglasses)이 있다.
  이 경우, eyewear를 입는 경우의 수는 2가지이다.
  • blue_sunglasses을 입거나, 아무 것도 입지 않는 경우.
• 이렇게 계산한다면 총 6가지의 경우의 수가 나오지만 여기에서 둘다 아무 것도 입지 않는 경우를 제외해야 한다.
• 문제의 조건에서는 적어도 하나의 의상은 입어야 하기 때문..
  따라서, 위에서 계산한 총 경우의 수 6에서 아무 것도 입지 않는 경우 1가지를 빼야 한다.
• 따라서, 최종적으로 가능한 조합의 수는 6 - 1 = 5가 된다.

문제 설명

• 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 몇 가지인지 알아보고자 합니다.
• 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다.
• 원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
• 원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 반환해주세요.
• 제한 사항
  • 3 ≤ elements의 길이 ≤ 1000
  • 1 ≤ elements의 원소 ≤ 1000
• 입출력 예시

문제 풀이

def solution(elements):
    # 원형 수열을 처리하기 위해 elements 리스트를 두 배로 확장
    extended_elements = elements + elements
    unique_sums = set()  # 부분 수열의 합을 저장할 집합

    n = len(elements)  # 원래 수열의 길이

    # 부분 수열의 길이를 1부터 n까지 증가시키며 처리
    for length in range(1, n + 1):
        # 각 길이에 대해 시작 위치를 0부터 n-1까지 증가시키며 처리
        for start in range(n):
            # 부분 수열의 합을 계산
            part_sum = sum(extended_elements[start:start + length])
            # 집합에 합을 추가
            unique_sums.add(part_sum)

    # 중복을 제거한 부분 수열의 합의 개수를 반환
    return len(unique_sums)

문제 풀이 과정

1. 원형 수열에서 처음과 끝이 연결된 부분 수열을 쉽게 처리하기 위해 수열을 두 배로 확장한다. 
   [7,9,1,1,4,7,9,1,1,4]
2. 부분 수열의 길이를 1부터 원래 수열의 길이까지 변화시키면서 모든 가능한 시작 위치에서 부분 수열의 합을 계산한다.
3. 계산된 모든 부분 수열의 합을 집합(set)에 저장하여 중복을 제거한다.

문제

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한조건

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

 입출력 예

풀이

1. 이 문제는 tangerine 배열을 보고 각각의 귤의 크기가 얼마인지를 보고난 후,  크기를 최대한 비슷하게 해야 하므로 같은 크기의 귤이 몇개인지를 카운트 해준 다음에 크기가 같은 귤이 많은 순서로 k 개의 귤을 담는 문제이다.

2. 먼저 tangerine 배열에서 각 숫자가 몇번 중복되는지를 알아낸 후, 최대한 적은 종류로 k 개를 담아 낼 수 있도록 중복되는 수를 담은 배열을 내림차순으로 정렬해서 몇 종류를 담으면 되는지 출력하면 된다.

1. Counter를 이용하여 같은 크기가 몇번 중복되었는지 확인한다.

Counter([1, 3, 2, 5, 4, 5, 2, 3])는 {1: 1, 3: 2, 2: 2, 5: 2, 4: 1}를 반환

2. most_common을 이용하여 최빈값 순서로 정렬한다.

Counter(tangerine).most_common()은 [(3, 2), (2, 2), (5, 2), (1, 1), (4, 1)] 튜플을 정렬된 리스트로 반환

3. 그 후  k보다 크거나 같을 때 몇 종류의 귤이 담겼는지를 리턴해준다.

from collections import Counter

def solution(k, tangerine):
    answer = 0

    for c in Counter(tangerine).most_common():
        k -= c[1] 

        answer += 1

        if k <= 0:
            break

    return answer

6
10 20 10 30 20 50

4

처음에 이문제는 그냥 중복 제거후 오름차순으로 구현했었다. 
하지만 이 문제의 가장 큰 문제는 증가된 부분 수열이고 이게 이 문제의 가장 큰 힌트였다.

즉, 이 문제는

1. 리스트 내 하나의 수를 기준으로 잡고 그 뒤에 나오는 값들을 비교하면서 오름차순으로 증가되는 수열을 찾는 것이다. 그래서 만약 주어진 값이 [5,1,6,2,7,3,8] 이렇게 있으면 

2. '5'을 기준으로 증가된 수열을 찾는다면 [5,6,7,8] 이 나올 것이고, '1'을 기준으로 잡는다면 [1,2,3] 나올 것이다.

3. 하지만 이렇게 구현한다면 단점이 생긴다.

만약 주어진 값이 [1,3,4,2,3,4] 일 경우 '1'을 기준으로 잡는다면 [1,3,4] 와 [1,2,3,4]가 나올 것이다.  

4. 그래서 이 문제는 DP를 사용해서 풀어야 겠다고 생각을 했고 DP문제는 거의 max(), min()이 나오기 때문에 코드를 작성했다.

-> DP문제는 이전에 계산된 값을 재사용해서 해결하는 방식이고 나는 상향식 접근법을 이용해 for문으로 구현했다. 그러기 위해서는 결과를 저장하는 TABLE이 필요하다. 이걸 나는 dp라는 리스트를 만들었다. 

5. 기준을 잡은 숫자와 그 이전의 숫자의 DP 배열의 값을 비교하여 문제를 풀면된다.

n = int(input())
a = list(map(int, input().split()))

dp = [0] * n 
for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))

코드 설명

입력값 : n = 6

입력값 : a = [10, 20, 10, 30, 20, 50]

dp = 초기값 : [0, 0, 0, 0, 0, 0, 0]

        for문을 다 돌고 난 뒤 : [1, 2, 1, 3, 2, 4]

1. dp 라는 이름의 리스트를 만들고 0으로 초기화를 한다. => dp = [0,0,0,0,0,0]

2. 첫번째 for문으러 값을 지정해준다 .

3. 두번째 for문으로 지정한 값을 이전값들과 비교해준다.

4. if 문에서 a[i] > a[j]는 지정한 값이 이전 값보다 커야하고 dp[i] < dp[j]는 현재 값이 이전 값보다 작으면 현재 dp리스트에 이전 dp 값을 지정한다.

5. for문이 다 돌면 dp[i]에는 0 또는 i 이전의 j 중 dp 값이 큰 dp[j]의 값이 들어 있을 것이다.

6. 그리고 dp[i]에 1을 더해주고 

7. dp값중 가장 큰 값을 출력해준다.

3번 과정의 자새한 풀이

# i = 0일 때 , a[0] = 10, dp = [1, 0, 0, 0, 0, 0]
# i = 1 , a[1] = 20, a[1] > a[0] 이고 dp[1] < dp[0] 이므로 dp = [1, 2, 0, 0, 0, 0]
# i = 2 , a[2] = 10, a[2] > a[0] 은 거짓이므로 dp = [1, 2, 1, 0, 0, 0]

# i = 3,

.

.

.

이렇게 풀면 결국에 dp =  [1, 2, 1, 3, 2, 4이 남게 될 것이고 이 중 가장 큰 값을 출력해주면 된다.

코딩테스트 연습 - 올바른 괄호 | 프로그래머스 스쿨 (programmers.co.kr)

답

def solution(s):
    stack = []
    for i in s:
        if i == '(':
            stack.append(i)
        else:
            if stack == []: 
                return False
            else:
                stack.pop()
    if stack != []: 
        return False
    return True

Stack을 이용하여서 “좌측 괄호” 일 경우 Stack에 넣어두고 “우측 괄호”가 나오면 Stack에 저장되어 있는 좌측 괄호 값을 빼는 형태로 짝을 찾아가는 형태로 구성

1. 문자열을 문자 배열로 구성하여 반복문 순회
2. 순회하면서 좌측 괄호인 경우는 Stack에 넣기
3. Stack 값이 비었을 경우 false 리턴 ⇒ 짝이 맞지 않는 경우
4. 순회하면서 우측 괄호인 경우 Stack에서 빼기
5. 순회가 끝나고 Stack에 값이 존재하지 않으면 false 리턴

문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제 핵심

1. n * m 크기의 maps가 주어지고 maps에서 0은 벽을 1은 길을 나타낸다.

2. 목표지점은 maps의 우측 하단 끝 지점이며 시작지점은 (1,1) 이다.

3. 캐릭터는 상하좌우로 움직일 수 있으며, 벽으로 이동하는 것은 불가능하다.

4. 목표지점에 도달하기 위해 최소한의 움직임을 구하기

첫 번째 방법

최단거리를 구하는 문제이기에 BFS탐색법을 사용했지만 시간 초과가 발생하였다..ㅎㅎ

def solution(maps):
    w = len(maps) - 1 
    h = len(maps[0]) - 1 
    visit = [] 
    going = [[0,0,1]] 
    while going:
        now = going.pop(0) 
        x, y, count = now[0], now[1], now[2] 
        if x == w and y == h: 
            return count
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: 
            nx = x + dx
            ny = y + dy
            if 0 <= nx <= w and 0 <= ny <= h and [nx, ny] not in visit and maps[nx][ny] == 1:
            
                going.append([nx, ny, count + 1]) 
                visit.append([nx, ny]) 
    return -1

기본적인 BFS 문제는 풀이방법이 비슷하다.
1. BFS문제면 이동할 때 사방팔방 다 이동하고 그 값을 저장하는 변수 필요 => 큐 사용

2. 위로 이동하고 좌우 옆으로 이동했을 때 해당 좌우가 방문했는지 저장하는 변수 필요  => 좌, 우, 상, 하 이동

1. 목표지점을 계산하기 위한 maps의 세로 길이와 가로 길이를 w ,h 로 정의

2. visit라는 방문한 지점을 담을 리스트 정의

3. going은 방문해야할 지점을 담을 리스트

4. now 는 현재 지점이고 x, y, count 는 현재 x, y좌표 및 이동 거리

5. 만약 목표지점일 경우 이동 거리를 리턴

6. dx, dy 에는 (1, 0), (-1, 0), (0, 1), (0, -1) 상하좌우 이동의 값을 넣고

7. 경계 및 벽에 막히지 않고, 방문한 지점이 아닐 경우 방문할 지점에 추가하고 방문한 지점에 추가

8.  모든 경로를 탐색후에도 만족하지 않으면 -1 리턴

그래서 뭐가 문제인가.. 알아봤는데 나는 방문한 지점을 담은 리스트 visit를 리스트로 사용했고 이 경우에서 방문 여부를 확인하는 로직인 not in을 사용할 경우 시간복잡도가 크게 상승한다는 얘기.. 이를 해결하기 위해 visit를 set로 선언하여 통과하였다.

두 번째 방법

def solution(maps):
    w = len(maps) - 1
    h = len(maps[0]) - 1
    visit = set() 
    going = [[0,0,1]]
    while going:
        now = going.pop(0)
        x, y, count = now[0], now[1], now[2]
        if x == w and y == h:
            return count
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx <= w and 0 <= ny <= h and (nx, ny) not in visit and maps[nx][ny] == 1:
                going.append([nx, ny, count + 1])
                visit.add((nx,ny))
    return -1

set 자료형의 경우 내부 해시테이블을 이용하여 포함여부를 확인할 때 리스트보다 빠른 속도로 확인이 가능하여 시간을 줄여 해결할 수 있었다.

세 번째 방법

뭔가 내가  쓴건 깔끔하지 않다고 해야하나.. 그래서 다른 사람 코드를 봤더니

going 리스트도 deque를 사용하여 속도를 더욱 줄이는 방법이 있고 깔끔했다.

from collections import deque
def solution(maps):
    w = len(maps) - 1
    h = len(maps[0]) - 1
    visit = set()
    going = deque([[0,0,1]]) 
    while going:
        now = going.popleft()
        x, y, count = now[0], now[1], now[2]
        if x == w and y == h:
            return count
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx <= w and 0 <= ny <= h and (nx, ny) not in visited and maps[nx][ny] == 1:
                going.append([nx, ny, count + 1])
                visit.add((nx,ny))
    return -1

deque를 사용하면 기존의 pop(), append()의 시간복잡도가 O(N)에서 popleft()를 통한 시간복잡도 O(1)로 줄어들기 때문에 n이 커질 경우 더욱 빠르게 문제해결이 가능해진다.