문제 링크 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 접근법 DFS로 원소를 넣는 경우와 넣지 않는 경우를 탐색한다. (조합) DFS로 탐색하면서 입력 개수에 도달하면 원하는 답인지 확인한다. 이렇게 안하고 매 순간마다 if(sum== answer)을 확인하면 return구분이 복잡해진다. 또한 dfs 탐색으로 깊이를 끝까지 탐색해야 이 문제에서 완전 탐색으로 답을 구할 수 있다. private static void dfs(int idx, int sum) { // df..
문제 링크 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 접근법 이 문제는 일반적인 DFS 문제처럼 풀면 조금 어려울 수 있다. DFS의 재귀(스택) 원리를 정확히 이해하고 그래프의 구조를 파악할 수 있어야 쉽게 풀 수 있다. 문제를 정리하면 친구끼리의 관계는 그래프에서 간선으로 나타낼 수 있다. 앞으로 간선 =관계 라는 것을 알고 있으면 다른 문제에도 그래프 탐색을 고려해봐야 한다. DFS로 리스트에 정점을 넣고 DFS로 깊이가 4인 곳을 찾으면 되는데 문제는 입력값이 트리와 그래프 모두 주어진다. 이 문제를 일반적인 트리로 접근하면 입력 테케 2에서 틀린다. 트리는 두 개의 노드 사이에 1개의 경로만을 가지며 ..
문제 링크 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 접근법 노드의 개수 N (1
문제 링크 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 트리 특성을 이해하고 있는지 물어보는 그래프 탐색 문제 입니다. DFS 핵심 문제 중 하나이고 트리의 성질까지 활용할 수 있는 좋은 문제였습니다. 한칸씩 앞으로 전진밖에 못하는 규칙때문에 어떤 게임말을 움직이는 것이 중요한 것이 아닌 누가 먼저하는지가 중요했습니다. 간선의 총합을 일자 직선으로 나타낼 수 있어 결국 긴 직선에서의 턴제였습니다. 리프노드의 깊이가 간선 개수랑 같았습니다. 다시 말하면, 리프노드 깊이의 총 합 = 모든 노드의 간선의 개수 게..
문제 링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP로 점화식을 만들어 풀 수 있지만 DFS로 풀어봤습니다. 문제에서 중요 포인트가 2로 나누어 떨어질 때나 3으로 나누어질 때 반드시 나누기 2나 나누기 3 연산을 하지 않아도 됩니다. 연산 조건을 만족할 때 그 연산을 반드시 실행하지 않아도 된다는 것만 아시면 됩니다. 또 중요한 포인트가 DFS는 불필요한 곳까지 탐색하여 최솟값을 찾을 때 반드시 백트레킹(= 가지치기) 방법을 써야합니다. 아래 해당 코드입니다. // 백트래킹 (가지치기) if(min count ? count : min; return; } // 백트래킹 (가지치기) if(min
문제 링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 삼성 역량평가 IM 수준의 대표 문제입니다. 4방탐색과 DFS를 이용하는 (2차원 배열) 그래프 탐색문제입니다. dfs에서 경계값 체크, 배추가 있는지, 방문 체크 3가지 조건만 넣어준다면 쉽게 풀 수 있습니다. private static void dfs(int y, int x) { visited[y][x] =true; for(int k =0 ; k< dx.length; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if(nx..
문제링크 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 전형적인 DFS 기본 문제였다. 그래프의 간선 연결을 2차원 배열에 표시하여 DFS로 표시된 곳을 탐색하고 방문 처리해줬다. 바이러스가 1번부터 점염되서 DFS에 인자를 1부터 시작해줬다. 출력할 때는 처음 감염시킨 1번 컴퓨터는 제외라고 문제에 적혀 있어서 answer-1을 해줬다. 성능 요약 메모리: 11612 KB, 시간: 76 ms 분류 그래프 이론(graphs), 그래프 탐색(gr..
문제링크 : https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 삼성 역량평가 IM 수준의 대표 문제입니다. 4방탐색과 BFS, DFS를 이용하는 (2차원 배열) 그래프 탐색문제이다. 백준 게시판을 살펴보니, 이 문제의 가로, 세로 입력을 잘못해서 물어보는 경우가 많았다. public class 이차원배열 { public static void main(String[] args) { int N = 4; // 가로 int M ..