dfs

📖 문제 https://www.acmicpc.net/problem/2668   💡  풀이 방식• DFS1. 위쪽 줄의 숫자들을 출발지로, 아랫 줄의 숫자들을 도착지로 한 그래프를 생성한다.2. 그래프 내에서 생성된 사이클을 찾고, 사이클을 만드는  숫자를 리스트에 넣고 오름차순 정렬해 출력한다.  - 사이클 발생 여부 확인 : [DFS] 출발 숫자 > arr[출발 숫자] > arr[arr[출발 숫자]]  - 탐색하다가 출발 숫자를 다시 만나면 사이클 하나가 완성된 거고, 이 값을 리스트에 넣는다.   🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950import java.util...

📖 문제 https://www.acmicpc.net/problem/1240   💡  풀이 방식• BFS 1.  인접 리스트를 만들고 N-1개의 연결 정보를 양방향으로 저장한다.2. M개의 노드 쌍에 대해 첫 번째 노드부터 두 번째 노드까지의 거리를 구한다. (BFS)   🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576import java.util.*;import java.io.*; public class Main {    static int N,M;    static ListNode>[..

📖 문제 https://www.acmicpc.net/problem/7490   💡  풀이 방식• 브루트포스 + 백트래킹 + 문자열 [DFS 함수]- 인자: now - 현재 탐색 중인 숫자의 위치 (1부터 시작) / num - 현재 숫자 / sign - 현재 숫자의 부호 (1이면 +, -1이면 -) / sum - 현재까지의 합계 / str - 현재까지의 연산식- 종료 조건: 수열의 맨 마지막 숫자 N에 도달했을 경우- 부호가 [공백이냐/+냐/-냐] 에 따라 재귀함수를 호출한다.   🔺 코드1234567891011121314151617181920212223242526272829303132333435import java.util.*;import java.io.*; public class Main {   ..

📖 문제 https://www.acmicpc.net/problem/16943   💡  풀이 방식• 백트래킹 백트래킹으로 정수 A에 포함된 숫자들의 순서를 섞어 숫자 C를 만든다.이렇게 만든 숫자가 0으로 시작하지 않고, B보다 작은 경우, 정답과 비교해 더 큰 값으로 정답을 갱신한다.  💥 유의사항새롭게 만든 C를 문자열로 봤을 때 0으로 시작하는지 확인해야 한다.  🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657import java.util.*;import java.io.*; public class Main {    static String[] st..

📖 문제 https://www.acmicpc.net/problem/15723   💡  풀이 방식• 플로이드-워셜 i는 k고, k는 j면, i는 j다. - N개의 전제를 입력받으며 a는 b라고 처리한다. → connected[a][b] = true- 플로이드-워셜로 i는 k고, k는 j면, i는 j 가 되도록 처리한다.- M개의 결론이 맞는지 확인하며 a는 b라면(= connected[a][b] == true) T를, 아니라면 F를 출력한다.   🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import java.util.*;import java.io.*; public class Mai..

📖 문제  프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• DFS필요 자료구조- 해당 응모 사용자 ID를 사용할지 판별 용 1차원 boolean형 배열- 현재까지 선택된 응모한 사용자 ID의 조합 집합 Set> result🔥  [제재 ID 목록 만드는 메소드 dfs(선택된 응모 사용자 ID 갯수, 현재까지 선택된 사용자 ID의 집합)]. 종료 조건 : 불량 사용자 갯수만큼 뽑았을 때, 여태 구한 제재 ID 경우를 집합에 넣는다.. 그만큼 뽑지 않았다면, 응모한 사용자 ID 배열을 돌면서 해당 사용자 ID와 현재 탐색 중인 불량 사용자..

📖 문제 https://www.acmicpc.net/problem/1967  💡  풀이 방식• DFS (트리)1. 2차원 인접 리스트 배열을 만들어 정보를 입력받는다. (양방향으로!)2. 1~N번의 모든 노드에서 DFS를 수행해 거리(가중치들의 합 = 트리의 지름)를 계산한다.for(int i = 1 ; i     [DFS 함수]현재 정점과 연결된 모든 점을 방문하며 가중치를 더하고, 이를 최댓값과 비교해 정답을 가장 큰 값으로 갱신한다.private static void dfs(int idx, int sum) { answer = Math.max(answer, sum); for(Node next : list[idx]) { if(!visited[next.idx]) { ..

📖 문제   18428번: 감시 피하기NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복www.acmicpc.net   💡  풀이 방식• 조합(DFS) + BFS 1. 격자를 입력받으면서 학생 S의 위치, 선생님 T의 위치, 빈 칸 X의 위치를 각 리스트에 저장해둔다.이러면 나중에 완전탐색으로 학생, 선생님, 장애물 위치를 따로 안 찾아도 된다.for(int i = 0 ; i   2. 빈 칸 X의 위치들 중 3개를 뽑고, 해당 위치에 장애물을 심었을 때 모든 학생들이 감시를 피할 수 있는지 BFS로 탐색한다.private static void dfs(int..

📖 문제   10026번: 적록색약적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)www.acmicpc.net   💡  풀이 방식• BFS 일반인과 적록색약의 경우를 나눠서 BFS를 수행한다.1) 일반인의 경우, RGB를 3색을 각각 다르게 본다. R구역과 G구역과 B구역으로 나뉜 구역 수를 구하는 BFS를 수행한다.visited1 = new boolean[N][N];for(int i = 0 ; i private static void bfs1(int x, int y, char c) { Queue q = new ArrayDeque(); q.ad..