스택: 선입후출, 후입선출의 구조 , 박스 쌓기
큐: 선입선출의 구조, 대기줄 서기
재귀함수: 자기 자신을 호출하는 함수
def recursive_function():
print("재귀 함수 호출")
recursive_function()
recursive_funciton()
그래프: 노드와 간선으로 이루어진 구조, 트리 구조같은, 도로와 도시가 연결된 것 같은 구조
그래프 표현 방식 :
: (Depth- First Search), 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
스택 자료 구조에 기초함
데이터 개수가 N 개인 경우 O(N) 시간 소요
#DFS 메서드 정의
def dfs(graph, v, visited):
#현재 노드를 방문 처리
visited[v]=True
print(v, end='')
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[i]:
if not visited[i]:
dfs(graph,i,visited)
#각 노트가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph=[
[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]
]
#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited =[False]*9
#정의된 DFS 함수 호출
dfs(graph,1,visited)
#1 2 7 6 8 3 4 5
: (Breadth First Search), 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
from collections import deque #큐 자료 구조 구현
#BFS 메서드 정의
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque([start])
#현재 노드를 방문 처리
visited[start]=True
#큐가 빌 때까지 반복
while queue:
#큐에서 하나의 원소를 뽑아 출력
v=queue.popleft()
print(v,end=" ")
#해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queqe.append(i):
visited[i] =True
#각 노드가 연결된 정보를 리스트 자료 형으로 표현 (2차원 리스트)
graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
#각 노드가 방문된 정보를 리스트 자료형을 표현(1차원 리스트)
visited= [False]*9
#정의된 BFS 함수 호출
bfs(graph, 1, visited)
#1 2 3 8 7 4 5 6
첫번째 줄에 얼음 틀의 세로 길이, N과 가로 길이 M 이 주어진다.(1 =<M,N=<1000)
DFS를 이용해 해결할 수 있다.
#입력 받기
n, m=map(int,intput().split())
graph=[]
for i in range(n):
graph.append(list(map(int,input())))
def dfs(x,y):
#주어진 범위 벗어나면 바로 종료
if x <= -1 or x>=n or y<= -1 or y >=n:
return False
#현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0:
#해당 노드 방문 처리
graph[x][y]=1
#상하좌우의 위치도 모두 재귀적으로 호출
dfs(x-1,y)
dfs(x,y-1)
dfs(x+1,y)
dfs(x,y+1)
return True
return False
#모든 노드(위치)에 대해서 음료수 채우기
result =0
for i in range(n):
for j in range(m):
#현재 위치에서 DFS 수행
if dfs(i,j) == True:
result +=1
print(result)
첫째 줄에 두 정수 N, M(4=<M,N=<200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0,1)로 미로의 정보가 주어진다. 각각의 수들은 공백없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다. 0은 벽, 1은 길
첫째 줄에는 최소 이동 칸의 개수를 출력한다.
from collections import deque
n, m =map(int,input().split())
graph=[]
for i in range(n):
graph.append(list(map(int, input())))
#상 하 좌 우
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def bfs(x, y):
#큐 구현을 위해 deque 라이브러리 사용
queue=deque()
queue.append((x,y))
while queue:
x,y =queue.popleft()
#현재 위치에서 네 방향으로의 위치 확인
for i in range(4)
nx= x + dx[i]
ny= y + dy[i]
#미로 찾기 공간을 벗어난 경우 무시
if nx>=n or nx <0 or ny>=n or ny<0:
continue
#벽인 경우
if graph[nx][ny] ==0:
continue
#해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] =gragh[x][y]+1
queue.append((nx,ny))
#가장 오른쪽 아래까지의 최단 거리 반환
return graph[n-1][m-1]
#BFS를 수행한 결과 출력
print(bfs(0,0))
Reference
위 자료는 <이것이 코딩="" 테스트이다.="" with="" Python="">_ 나동빈 지음 을 바탕으로 공부한 내용입니다.