문제 링크 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 풀이 DFS로 접근했고 딱히 설명할 부분은 없는 것 같다. 굳이 하자면, 연결 요소를 구하는 문제이기 때문에 chk변수를 둬서, 방문하지 않은 곳에 첫 방문 시를 새로운 연결 요소가 있는 경우로 두고 풀었음. import java.io.BufferedReader; import java.io.IOException; impor..

문제 링크 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 풀이 DFS, BFS 둘 다 가능했지만, BFS에 조금 미숙하여 BFS로 진행하였다. 난이도가 쉬운 문제라 (실버 3?) 구현에 어려움은 없었다. 1에서 시작하여, chk와 연결되어있는 노드들의 방문여부를 체크하여 미방문 시 cnt++ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..

문제 링크 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 자신있는 DFS로 풀었고, BFS는 몇 번 해보지 않아 사용을 해보기로 했다. DFS import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BakJoon1012 { public static void ..

https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 DFS를 이용해서 간단하게 풀어냈다. class Solution { static int idx = 0; static int answer = -1; public int solution(String word) { dfs(word, ""); return answer; } public void dfs(String word, String text) { if(answer > 0) return; if(w..

https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이제 어느정도 기본 DFS문제는 감이 온 것 같다 백트래킹으로 던전 탐사가 가능한 최대값을 구해줬다. class Solution { static int join = 0; public int solution(int k, int[][] dungeons) { boolean[] bl = new boolean[dungeons.length]; dfs(dungeons, bl, 0, k, 0, 0); re..

https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1. DFS를 활용한 백트래킹을 통해 모든 경우의수 체크 2. 소수일 경우 중복을 거르기 위한 Set 사용 두가지를 메인으로 잡고 풀었다. import java.util.*; class Solution { static Set set = new HashSet(); char[] ch = new char[] {}; boolean[] bl = new boolean[] {}; public int so..

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [알고리즘] 깊이 우선 탐색(DFS) [알고리즘] 깊이 우선 탐색(DFS) 깊이 우선 탐색 ( Depth-First Search ) 루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징 1. 모든 노드를 방문하고자 하는 경우에 사용한다. 2. 단순 검 mag1c.tistory.com 프로그래머스 기준 전반적인 2레벨 문제나, 적당한 3레벨문제 정도..

깊이 우선 탐색 ( Depth-First Search )루트 노드에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 특징1. 모든 노드를 방문하고자 하는 경우에 사용한다.2. 단순 검색 속도는 너비 우선 탐색(BFS)에 비해 느리다.3. 검색이 아닌 순회를 할 경우 많이 사용한다.공통 상위를 가지는 아래 리프 노드들을 한방에 잘라내는게 가능하기 때문에 백트래킹에 사용된다.미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.  장점1. 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 비교적 적다.2. 목표 노드가 깊은 단계에 있을 ..