5-4) 미로탈출
BFS 이용 혼자 못풀었음 import sys from collections import deque sys.stdin = open("./input/5-11)input.txt", "r") T = int(input()) 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): queue = deque() queue.append((x,y)) # 큐 빌때까지 while queue: x,y = queue.popleft() # 네 방향으로 위치 확인 for i in range(4): nx = x+dx[i] ny = ..
5-2) 탐색 알고리즘 DFS / BFS
DFS (Depth-First Search) 깊이 우선 탐색 스택 or 재귀함수 이용 깊은 노드 우선 탐색 동작과정 ① 탐색 시작 node - 스택에 삽입, 방문 처리 ② 스택 최상단 node - 미방문 인접 node O, 스택에 넣고 방문 처리. 미방문 인접 node X, 스택에서 최상단 node pop ③ 위 과정 반복 def dfs(graph, v, visited): # 현재 노드 방문처리 visited[v] = True print(v, end=' ') # 인접 노드 재귀적 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드 연결된 정보 (2차원 리스트) graph = [ [], [2,3,8], [1,7], [1,4,5], ..
DFS
DFS (Depth-First Search) 깊이 우선 탐색 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프 연결 관계 표현 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계 표현 # 인접 행렬 INF = 999999999 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] # 인접 리스트 graph = [[] for _ in range(3)] # node 0 graph[0].append((1,7)) graph[0].append((2,5)) # node 1 graph[1].append((0,7)) # node 2 graph[2].append((0,5))
4-3) 게임 개발
n,m = map(int, input().split()) x,y,d = map(int, input().split()) dx = [-1,0,1,0] dy = [0,1,0,-1] nx,ny = 0,0 cord = [[int(y) for y in input().split()]for x in range(n)] #print(cord) cnt = 1 cord[x][y] = -1 while 1: for _ in range(4): d = (d-1) % 4 nx = x+dx[d] ny = y+dy[d] if(cord[nx][ny] == 0): cord[nx][ny] = -1 x = nx y = ny #print(x,y) cnt += 1 break if (x==nx and y==ny): continue # 4방향 모두 이..
