본문 바로가기

코딩 테스트124

경쟁적 전염 p.345 import sys from collections import deque input=sys.stdin.readline n,k=map(int, input().split()) test=[] data=[] for i in range(n): test.append(list(map(int, input().split()))) for j in range(n): if test[i][j] != 0: # 바이러스 종류, 시간, 좌표x, 좌표y data.append((test[i][j],0,i,j)) s,x,y=map(int, input().split()) data.sort() q=deque(data) dx=[-1,1,0,0] dy=[0,0,-1,1] while q: virus, _s, _x, _y=q.poplef.. 2021. 1. 27.
연구소 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.

티스토리툴바