DFS5 [백준 - Java] 1987번 : 알파벳 문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 설명 DFS, 백트래킹을 이용해 구현 (0, 0)부터 시작해서 상하좌우 이차원 배열 범위를 넘지 않고, 방문하지 않았던 곳으로 이동 이동할 곳에 있는 알파벳이 지금까지 DFS를 돌며 만들어진 문자열 str에 포함되지 않는 문자라면 str에 추가하고 길이도 +1 가장 최장 길이를 구해야 하기 때문에 매 DFS마다 길이 length와 최장 길이를 저장할 ans의 값을 비교해 업데이트 해주.. 2021. 7. 16. [백준 - Java] 17142번 : 연구소3 문제 www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 설명 연구소1 문제와 비슷한 문제지만 조금은 다름. 기존 연구소 문제는 아래 포스트를 참고 [백준 - Java] 14502번 : 연구소 (삼성 SW 역량 테스트 기출 문제) 백트래킹으로 바이러스를 퍼뜨릴 수 있는 공간에 M개의 바이러스를 놓아 활성화시켜봄. M개의 바이러스를 활성화시켰다면 BFS로 바이러스를 퍼뜨림. 모든 빈칸에 바이러스를 퍼뜨렸다면 그때까지 걸린 시간 Math.min()으로 min 변수에 저장. .. 2021. 4. 21. [백준 - Java] 15684번 : 사다리 타기 문제 www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 설명 자잘한 실수도 많이 하고, 필요 없는 map을 만든다 거나, class로 좌표를 저장하고 ArrayList에 넣었다 뺐다, ArrayList를 복사하던가 삽질을 겁나 많이 했음. 막상 풀고나니 별거 없었고, 나는 4차원 배열까지 써서 해결했는데, 2차원 배열만 썼어도 됨... 삼성 SW역량테스트 기출문제인데, 나는 아마 주어진 3시간 동안 이 문제 계속 쩔쩔매다가 왔을 듯;;;;ㅜㅜ아웅ㅇ 열 받아!.. 2021. 4. 18. [Java] DFS로 모든 이동 경로 구하기 DFS를 이용해 출발지(시작 정점)에서 목적지(도착 정점)까지의 모든 경로를 구해보자. DFS에 대해 자세히 알고 싶다면 아래 포스트 참고 [Java] DFS 깊이 우선 탐색 - 인접 리스트 / 인접 행렬로 구현 더보기) 인접 행렬을 이용해 그래프를 구성한 기존의 DFS 구현 코드 더보기 import java.util.*; public class DFS { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 정점의 개수 int m = sc.nextInt(); // 간선의 개수 int v = sc.nextInt(); // 탐색을 시작할 정점의 번호 boolean visited.. 2020. 9. 23. [Java] DFS 깊이 우선 탐색 - 인접리스트 / 인접행렬로 구현 DFS 깊이 우선 탐색 (Depth Fisrt Search) "더 나아갈 길이 보이지 않을 때까지 깊이 들어간다"를 원칙으로 그래프 내의 정점을 방문하는 알고리즘이다. 미로 찾기처럼 그래프의 정점을 타고 깊이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어있는 정점을 타고 방문을 재개하는 방식으로 동작한다. * 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 * 사용하는 경우: 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. (완전 탐색 알고리즘에 자주 이용됨) DFS의 특징 자기 자신을 호출하는 순환 알고리즘의 형태 트리 순회(전위, 중위, 후위 순회.. 2020. 4. 25. 이전 1 다음 반응형
