dfs

문제 링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 전형적인 DFS, BFS 기본 문제. C로 리마인드할겸.. 가로, 세로 입력은 순서 헷갈리지 않게 항상 주의하자~ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

[알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기 사이클을 찾기 위해서는 DFS를 활용한다. (정점 : v, 간선 : e) - visited[] : 점들의 방문여부가 저장된 배열 - recur[] : v가 지금까지 방문한 점이 저장된 배열 for(v 수 만큼) { dfs(v, visited, recur) } DFS 수도코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 boolean dfs(v(a), visited, recur) { visited[v(a)] = true recur[v(a)] = true for(v(a)와 연결된 점의 수만큼) { b = 연결된 점 if(!visited[b] && dfs(v(b), visited, recur){ // b가 방문상태..

[백준 11559] Puyo Puyo (Java, DFS) 문제 출처 : 링크 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 약간의 DFS와 시뮬레이션이 합쳐진 문제다. 이런 문제 또한 약간의 제한조건만 달라지면서 많이 출제된다. 가장 중요한 건, 문제를 잘 이해하고 제한 조건을 하나라도 놓치지 않고 구현해야 한다는 점. 코드를 짜기 전에 먼저 종이에 확실히 조건을 모두 이해하며 로직을 간단하게 짜고 진행하자. 1. 맨 아래부터 블럭이 쌓여있기 때문에, 배열에서 아래부터 체크하며 빈칸이 아닌 것(알파벳인 곳)을 list에 담는다. 2. list에 담은 걸 하나씩 뽑아 해당 위치에서 DFS를 돌리..

[SWEA 1767] 프로세서 연결하기(Java) 문제 출처 : 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! www.swexpertacademy.com 2차원 배열 안에 설치되어 있는 코어에 전선을 연결시키는 문제다 벽에 붙어있는 코어는 전선을 연결할 수 없고, 나머지 코어를 최대한 많이 활용하면서 최소한의 전선 길이를 출력해야하는 문제다 최소한의 전선 길이라는 말로 BFS로 접근하면 힘들어지고, 코어를 많이 가져가기 위해 DFS 탐색 접근이 편하다 우선 코어에 해당하는 1의 값이 들어오면, 벽에 붙어있지 않은 코어들을 list에 저장했다 그리고 dfs를 통해 해당 코어의 index와 코어의 수 coreCnt, 마지막으로 전선의 길이를 ..

[백준 14502] 연구소 (Java) 출처 : 링크 삼성 코테 기출 문제다. 0은 이동가능한 값, 1은 벽, 2는 바이러스다. 벽으로 막혀있지 않고, 바이러스와 인접해있는 0인 곳들은 모두 감염이 된다. 처음 시작 전에, 값이 0인 map에서 3곳에 벽을 세울 수 있다. 따라서 map에 저장된 0의 수를 저장하고, 조합을 통해 벽을 모두 세운 뒤 dfs를 진행했다. 모두 진행한 뒤 가장 많은 안전 영역 수를 출력해주면 되는 문제다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081..

[백준 16234] 인구 이동 (Java) 출처 : 링크 2018년 하반기 삼성 코테 기출이다. DFS와 BFS 모두 사용이 가능하고, 인구 이동이 가능할 때까지 계속 진행해서 횟수를 출력해주면 된다. 이동이 가능한 배열마다 같은 숫자를 저장하도록 2차원 배열을 하나 더 만들었다. (copymap) DFS를 통해 조건에 맞는 이동가능 배열끼리 묶어주고, 해당 map의 값을 모두 더해 평균을 내서 저장시켰다. 평균을 구하는 반복문을 따로 만들어서 사용하면 시간초과로 풀 수 없으므로 먼저 리스트를 생성해 DFS를 호출하는 반복문 안에서 평균 값 계산을 같이 해야 시간을 줄일 수 있었다. 12345678910111213141516171819202122232425262728293031323334353637383..

[알고리즘] 백트래킹(Backtracking) [알고리즘] 백트래킹(Backtracking) 백트래킹이란?모든 경우의 수를 검색하는 알고리즘'특정조건'을 만족하는 모든 경우의 수를 찾고 싶을 때 유용DFS(깊이 우선 탐색)을 기반으로 하는 알고리즘 후보해 집합에서 최적해 집합을 찾아내는 문제에 적용 가능!후보해 : 정답이 될 가능성이 있는 모든 조합최적해 : 문제의 답으로 기준을 만족하는 해 DFS는 Brute Force 알고리즘으로, 재귀함수를 통해 그냥 모두 다 검사해서 찾음 DFS와 백트래킹의 차이점은 '가지치기'가지치기를 이용하기 때문에 DFS처럼 모든 경우의 수를 확인하는 알고리즘은 아님! 가지치기는 어렵게 생각하지말고 반복문에서 break나 return에 해당한다고 생각하자 백트래킹 대표 문제..

[swexpert 2819] 격자판의 숫자 이어 붙이기 문제 출처 : 링크 4x4 말판에 0~9까지 임의의 수가 작성된다. 지나온 말판도 다시 지나갈 수 있는 것이 포인트. dfs로 접근하는데 방문하는 부분을 따로 지정하지 않으면 될 것 같다. 말판에서 총 6번 움직이면서 (처음에 시작하는 지점 포함) 총 7자리의 수가 만들어지면 저장한다 이때 모든 경우의 수를 진행하면서, 중복되는 부분은 없애고 총 몇 가지 수를 만들 수 있는 지 구해야하는 문제다. 숫자를 int로 만들지 않고, 그냥 문자열로 받아서 저장하는 방식으로 접근했다. HashSet에 저장하면, 중복되는 부분은 추가로 저장하지 않으므로 이 문제에서 사용하면 좋을 것 같아서 적용해봤다. 만약 ArrayList나 배열을 사용한다면, 저장 전에 조..

[백준 1012] 유기농 배추 (DFS, BFS) 문제 출처 : 링크 DFS와 BFS를 활용해서 모두 풀 수 있는 문제다. 1로 표시된 구간마다 묶어서 총 몇 개가 있는지 구해야 한다. 예전에 처음 공부하면서 풀었던 백준 2667번 단지번호 문제(링크)와 유사하다. DFS 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenize..