본문 바로가기

Algorithm/BFS DFS17

[프로그래머스] 가장 먼 노드 c++ BFS풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include #include #include #include using namespace std; vector v(50001); //간선벡터 bool visited[20001]; //방문여부 vector dist(20001); //최단거리 저장 (dist[3]인 경우 3까지의 최단경로) int max_dist; //최대거리 void bfs(int node){ queue q; visited[node] = true; q.push(node); while.. 2023. 2. 25.
[백준] 1987 알파벳 c++ Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include #include #include using namespace std; const int MAX = 21; int r, c; int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; int alpha[26]; char arr[MAX][MAX]; int answer; void dfs(int x, int y, int cnt) { answer = max(answer, cnt); for (int i = 0; i > r >> c; for (int i =.. 2023. 2. 24.
[백준] 바이러스 c++ Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include #include #include #include #include using namespace std; int answer; int m, n; bool visited[101]; vector v(101); void dfs(int node) { visited[node] = true; for (int i = 0; i > m; cin >> n; for (int i = 0; i > node1 >> node2; v[node1].push_back.. 2023. 2. 23.
[프로그래머스] 게임 맵 최단거리 c++ Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #include #include #include #include using namespace std; int m,n; //행,열 int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}}; bool visited[101][101]; int dist[101][101]; queue q; int solution(vector maps) { int answer = 0; int m = maps.size(); /.. 2023. 2. 23.
백준 1260 DFS와 BFS DFS와 BFS를 구현하는 문제이다. DFS의 경우 DFS(깊이우선탐색)은 자기자신을 호출하는 순환알고리즘의 형태를 갖는다. 재귀를 이용해서 구현!! 1번 노드에 인접한 모든 노드들에 대해서 간선이 있고, 방문하지 않았던 지점이라면 방문한다. 같은 방식으로 n개의 노드에 대해서 진행. BFS의 경우 BFS(너비우선탐색)은 재귀적으로 동작하지 않는다. 일반적으로 큐를 사용해서 반복적으로 구현한다. Prim, Dijkstra알고리즘과 유사하다. 큐를 이용해서 구현!!(FIFO방식) 1번노드에 인접한 모든 노드들에 대해서 간선이 있고 방문하지 않았던 지점이라면 방문하여 큐에 넣는다. 큐가 empty가 될 때까지 반복해서 진행. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17.. 2022. 2. 3.

티스토리툴바