본문 바로가기

코딩 테스트/DFS, BFS12

연구소 p.341 DFS import sys from itertools import combinations input=sys.stdin.readline n,m=map(int, input().split()) graph=[] temp=[[0]*m for _ in range(n)] fence=[] virus=[] result=0 for i in range(n): graph.append(list(map(int, input().split()))) for i in range(n): for j in range(m): if graph[i][j]==0: # 울타리 칠 수 있는 위치 fence.append((i,j)) elif graph[i][j]==2: #바이러스 위치 virus.append((i,j)) fence_c=list.. 2021. 1. 26.
특정 거리의 도시 찾기 p. 339 BFS import sys from collections import deque input=sys.stdin.readline n,m,k,x=map(int, input().split()) graph=[[] for _ in range(n+1)] for i in range(m): a,b=map(int, input().split()) graph[a].append(b) visited=[-1]*(n+1) visited[x]=0 def bfs(_x): queue=deque() queue.append(_x) while queue: now = queue.popleft() for i in graph[now]: if visited[i]==-1: queue.append(i) visited[i]=visited[no.. 2021. 1. 26.
미로 탈출 p.152 from collections import deque n,m = map(int, input().split()) graph=[] visited=[[False]*m for _ in range(n)] 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)) visited[x][y]=True while queue: x,y=queue.popleft() for i in range(4): #상하좌우 확인 nx=x+dx[i] ny=y+dy[i] if nx=m: continue elif graph[nx][ny]==0: continu.. 2021. 1. 25.
음료수 얼려 먹기 p.149 n,m=map(int, input().split()) graph=[] for i in range(n): graph.append(list(map(int, input()))) def dfs(x,y): # 범위를 벗어났을 때 if x=n or y=m: return False # 처음 방문한 노드일 때 if graph[x][y]==0: # 해당 노드를 방문처리 graph[x][y]=1 # 그래프의 상하좌우 호출 dfs(x,y-1) dfs(x,y+1) dfs(x-1,y) dfs(x+1,y) return True return False result=0 for i in range(n): for j in range(m): if dfs(i,j) == True: result+=1 print(result) 2021. 1. 25.
BFS p.146 BFS(Breadth First Search) : 너비 우선 탐색 * 큐를 사용(deque) * graph를 인접 리스트 사용 * visited로 방문했는지 여부 확인 [동작 과정] 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 2. 큐에서 popleft()를 하여 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 큐에 append 3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복 from collections import deque def bfs(graph, start, visited): queue=deque() queue.append(start) visited[start]=True # queue가 빌 때까지 반복 while queue: v=queue.popleft() print(v.. 2021. 1. 25.
DFS p.142 DFS(Depth First Search) : 깊이 우선 탐색 * 스택을 사용 = 재귀 함수 사용 * graph를 인접 리스트 사용 * visited로 방문했는지 여부 확인 [동작 과정] 1. 탐색 시작 노드를 스택에 삽입하고 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼내기 3. 2번 과정을 스택에 남아있는게 없을 때까지 반복 (일반적으로 인접 노드 중 방문하지 않은 노드가 여러개 있을 시, 번호가 낮은 순서부터 처리) def dfs(graph, v, visited): visited[v]=True print(v, end=' ') for i in graph[v]: if.. 2021. 1. 25.

티스토리툴바