dfs (6) 썸네일형 리스트형 [백준] 1800번: 인터넷 설치 - JAVA 🔗 문제 링크 BOJ 1800번: 인터넷 설치 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 📝 풀이 과정 처음에는 방문할 때마다 가격을 저장하고 해당 가격순으로 정렬하여 K개만큼 제외하는 등의 작업이 굉장히 오래걸렸기 때문에 당연하게도 시간초과가 발생했다... 계속 고민하며 아이디어가 떠오르지 않아 고생하던 중 한가지 힌트를 보게 되었다. 최소값을 미리 정한 뒤 탐색을 하라는 것이었다. 최소값을 x로 두고 가격이 x이하인 선은 그냥 연결을 하고, x이상인 선은 K개.. [백준] 1043번: 거짓말 - JAVA 🔗 문제 링크 BOJ 1043번: 거짓말 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 📝 풀이 과정 진실을 아는 사람이 한 사람이라도 파티에 있게 되면 해당 파티의 사람들은 모두 진실을 알게 된다. 따라서, 진실을 아는 사람과 파티에 참가한적 없는 사람끼리만 존재해야 거짓말을 할 수 있는 파티이다. 같은 파티에 참가한 사람들끼리 연결을 해준 뒤, 진신을 알게된 사람을 기준으로 DFS를 돌며 같은 파티에 참가한 사람들에게 모두 진실을 알려준다. 같은 파티에 참가한 사람들을 모두 진실을 알거나, 모르는 경우이기 때문에 .. [백준] 14500번: 테트로미노 - JAVA 🔗 문제 링크 BOJ 14500번: 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 📝 풀이 과정 모든 테트로미노를 그린 뒤 탐색마다 도형을 회전시키고 대칭시키며 구할 수도 있지만 경우의 수가 너무 많아 귀찮아서 포기하였다... 예시로 그려진 테트로미노의 모양을 잘 살펴보면 ㅜ모양을 제외하면 DFS로 표현이 가능할 것이라는 생각이 들었다. 회색으로 칠해진 부분이 현재까지 탐색한 부분이고 ⭐의 위치가 현재 위치라고 할 때, 탐색할 수 있는 방향은 파란색의 화살표로 가는 방향뿐이기 때문에 ㅜ 모양의 탐색.. [백준] 11724번: 연결 요소의 개수 - JAVA 🔗 문제 링크 BOJ 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 📝 풀이 과정 BFS와 DFS 모두 풀이가 가능하지만 DFS로 문제를 풀어보았다. 반복문을 돌며, 만약 방문한 요소가 아닐 경우 해당 칸을 시작으로 하여 DFS를 시작한다. 방문하며 visit을 true로 변경하여 다시 방문하지 않도록 방문처리를 해주고 해당 요소에 연결되어 있고 방문하지 않았다면 재귀를 통해 DFS를 돌린다. 더이상 방문할 요소가 .. [백준] 10026번: 적록색약 - JAVA 🔗 문제 링크 BOJ 10026번: 적록색약 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 📝 풀이 과정 반복문을 통해 순차적으로 접근하여 만약 방문하지 않은 점일때, 주변에 같은 색 영역이 존재하는 경우 방문처리를 해주면 되는 DFS, BFS 문제이다. 이번에는 DFS로 풀어보기로 했다. 이 문제에는 색약이 아닌 경우와 색약인 경우의 2가지의 탐색이 필요하다. 색약이 아닌 경우를 먼저 탐색하고 이후 색약인 경우를 탐색하기로 했다. 반복문을 돌며 해당 칸을 방문하지 않은 경우,dfs 메소드를 통해 해당.. [백준] 2606번: 바이러스 - JAVA 문제 링크 BOJ 2606번: 바이러스 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 과정 바이러스는 연결된 네트워크를 통해 모두 전파되므로 연결되어 있는 모든 경로를 탐색하면 되는 문제이다. DFS와 BFS 모두 가능하지만, 다른 문제를 풀면서 BFS를 더 많이 사용해서 이번에는 DFS를 사용해 문제를 풀어보기로 했다 dfs(int) 를 통해 방문한 노드를 넘겨주고, 만약 해당 노드를 방문했다면 return, 아니라면 연결된 노드를 다시 dfs로 탐색하였다. 방문한 노드의 visit값을 true로 변경하고.. 이전 1 다음
