dfs10

• 

  [Algorithm] (이코테) DFS/BFS - 미로 탈출 (Python/파이썬) ▶ 문제 설명 동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1) 이고 미로의 출구는 (N, M)이 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. - 입력 조건 : 첫째 줄에 두 정소 N, M(4 = m: continue # 벽인 경우 무시 if graph[nx][ny] == 0: continue # 해당 노드를 처음 방문하는 경우에만 최단 거리 기.. Developer/Algorithm 2023. 9. 5.

• 

  [Algorithm] (이코테) DFS/BFS - 음료수 얼려 먹기(Python/파이썬) ▶ 문제 설명 N X M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. - 입력 조건 : 1) 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 Developer/Algorithm 2023. 9. 5.

• 

  [Algorithm] (이코테) DFS/BFS - DFS (Python/파이썬) ▶ 문제 설명 한 그래프에서 노드 1과 노드 7이 연결되어 있는 상황을 생각해보자. 인접 행렬 방식에서는 graph[1][7] 만 확인하면 된다. 반면에 인접 리스트 방식에서는 노드 1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야 한다. 그러므로 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다. DFS는 탐색을 위해서 사용되는 탐색 알고리즘이라고 했는데 구체적으로 어떻게 동작할까? DFS는 깊이 우선 탐색 알고리즘이라고 했다. 이 알고리즘은 특정한 경로로 탐색하다가 특정환 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처.. Developer/Algorithm 2023. 8. 30.

• 

  [Algorithm] (이코테) DFS/BFS - 인접 리스트 예제 (Python/파이썬) ▶ 문제 설명 인접 리스트 예제 ▶ Code # 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현 graph = [[] for _ in range(3)] # 노드 0에 연결된 노드 정보 저장 (노드, 거리) graph[0].append((1, 7)) graph[0].append((2, 5)) # 노드 1에 연결된 노드 정보 저장 (노드, 거리) graph[1].append((0, 7)) # 노드 2에 연결된 노드 정보 저장 (노드, 거리) graph[2].append((0, 5)) print(graph) ▶ Point 인접 리스트 정의 확인 Developer/Algorithm 2023. 6. 2.

• 

  [Algorithm] (이코테) DFS/BFS - 인접 행렬 예제 (Python/파이썬) ▶ 문제 설명 인접 행렬 예제 ▶ Code INF = 999999999 # 무한의 비용 선언 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) ▶ Point 인접 행렬의 정의 확인 Developer/Algorithm 2023. 6. 2.

• 

  [Algorithm] (이코테) DFS/BFS - 2가지 방식으로 구현한 팩토리얼 예제 (Python/파이썬) ▶ 문제 설명 2가지 방식으로 구현한 팩토리얼 예제 ▶ Code # 반복적으로 구현한 n! def factorial_iterative(n): result = 1 # 1부터 n까지의 수를 차례대로 곱하기 for i in range(1, n + 1): result *= i return result # 재귀적으로 구현한 n! def factorial_recursive(n): if n Developer/Algorithm 2023. 6. 2.

• 

  [Algorithm] (이코테) DFS/BFS - 재귀함수의 종료 조건 예제 (Python/파이썬) ▶ 문제 설명 재귀함수의 종료 조건 예제 ▶ Code def recursive_function(i): # 100번째 호출을 했을 때 종료되도록 종료 조건 명시 if i == 100: return print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.') recursive_function(i + 1) print(i, '번째 재귀함수를 종료합니다.') recursive_function(1) ▶ Point 재귀함수의 종료 조건 확인 Developer/Algorithm 2023. 6. 2.

• 

  [Algorithm] (이코테) DFS/BFS - 무한히 반복되는 재귀함수 예제 (Python/파이썬) ▶ 문제 설명 무한히 반복되는 재귀함수 예제 ▶ Code def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() ▶ Point 재귀함수의 정의 확인 Developer/Algorithm 2023. 6. 2.

• 

  [Algorithm] (이코테) DFS/BFS - 큐 구현 예제 (Python/파이썬) ▶ 문제 설명 큐 구현 예제 ▶ Code from collections import deque # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque() # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() print(queue) # 먼저 들어온 순서대로 출력 queue.reverse() # 다음 출력을 위해 역순으로 바꾸기 print(queue) # 나중에 들어온 원소부터 출력 ▶ Point .. Developer/Algorithm 2023. 6. 2.

• 

  [Algorithm] (이코테) DFS/BFS - 스택 구현 예제 (Python/파이썬) ▶ 문제 설명 스택 구현 예제 ▶ Code stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력 ▶ Point stack의 정의 확인 Developer/Algorithm 2023. 6. 2.