Algorithm 💡/DFS28 [백준 2667번] 단지번호붙이기 n = int(input()) # 2차원 배열 지도 arr = [] # 방문 여부 확인용 2차원 배열 visited =[[False]*n for _ in range(n)] # 단지 내 가구 수 count = 0 # 단지 내 가구 수 리스트 count_list = [] for i in range(n): arr.append(list(map(int,list(input())))) # dfs 함수 def dfs(x,y): global count # 집이 존재한지 / 방문한 적 있는지 여부 확인 if arr[x][y] == 1 and not visited[x][y]: # 방문 처리 visited[x][y] = True # 단지 내 가구 수 증가 count += 1 # 상-하-좌-우로 이동하기 위한 값 nx = [-.. 2023. 2. 13. [백준 2606번] 바이러스 from collections import deque vertex_count = int(input()) edge_count = int(input()) graph = [[] for _ in range(vertex_count + 1)] for _ in range(edge_count): x, y = map(int,input().split()) graph[x].append(y) graph[y].append(x) visited = [False] * (vertex_count+1) count = 0 def dfs(graph, v, visited): global count visited[v] = True count += 1 for i in graph[v]: if not visited[i]: dfs(graph,i,vis.. 2023. 2. 12. [백준 1260번] DFS와 BFS from collections import deque n, m ,v = map(int,input().split()) graph = [[] for _ in range(n+1)] visited_dfs = [False] * (n+1) visited_bfs = [False] * (n+1) # 노드와 간선 정보 받기 for _ in range(m): x, y = map(int,input().split()) graph[x].append(y) # 두 정점 사이의 간선은 양방향이므로 양방향으로 저장 graph[y].append(x) # 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것 부터 방문해야 하므로 # 각 노드마다 정렬 for i in graph: i.sort() # DFS 함수 구현 def dfs(.. 2023. 2. 12. [DFS] DFS 알고리즘의 기본 개념 및 활용법 DFS DFS는 Depth-First Search, 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프의 기본 구조: 노드(Node) or 정점(Vertex) 간선(Edge) 그래프의 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 두 노드는 인접(Adjacent)하다고 표현한다. 프로그래밍에서는 그래프를 크게 2가지 방식으로 표현할 수 있는데, 코딩테스트에서는 이 2가지 방식 모두 필요하니 두 개념에 대해 확실하게 알고 있도록 하자. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계.. 2023. 2. 10. 이전 1 2 3 4 5 다음
