갱스터하우스

➡️문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/43162 💡아이디어BFS, DFS, 그래프탐색! 사실 알고리즘고득점 kit의 깊이/너비 우선 탐색(DFS/BFS)에 있는 문제여서문제의 유형이 무엇인지는 이미 알고 있었다 그래도 문제에서"컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다." 라는 부분을 읽고, 타고타고가 가능하네? -> 그럼 1부터 N까지 각 정점을 탐색하면서 하나의 정점에서 방문할 수 있는 노드를 다 방문하자-> ..

➡️문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/43165 💡아이디어DFS ✏️문제 풀이1. DFS - 성공문제를 읽다보면 결국 numbers 배열 안의 원소들이어떨 때는 +로, 또 어땔 때는 -로 더해지는 것을 확인할 수 있다그래서 이 두 가지 경우로 나누어 dfs를 돌리며이 때, 현재 몇 번째 원소를 더해야하는지와 이전까지의 합을 매개변수로 설정한다.그 뒤로는 배열의 마지막까지 도달하면 합이 target과 같은지 확인하고 return!import java.util.*;/*dfs 접근해보기*/class Solution { static int answer = 0; static int[] numbers; static ..

1. DFS(Depth-First Search) 깊이 우선 탐색 : 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 동작 원리 : 스택(Stack) 구현 방법 : 재귀함수 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘 1.1 구체적인 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 최상단 노드 꺼내기 2-3번의 과정을 더 이상 수행할 수 없을때까지 반복 '방문처리'란? 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것! = 1노드 1삽입 # graph : 탐색할 그래프..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 설명 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤..