본문 바로가기

DFS14

[백준] 11725번: 트리의 부모 찾기 (Java) 1. 문제설명트리의 루트를 1이라고 정했을 때, 주어진 트리에서 각 노드의 부모를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식=> DFS와 BFS 모두 풀이 가능하다.인접 리스트를 사용해 트리의 노드 정보를 저장한다.각 노드를 탐색하며 DFS를 사용해 각 노드의 부모를 저장한다.방문 체크하는 `visited` 배열 사용부모 정보 저장하는 `parent` 배열 사용 3. 최종 코드import java.io.*;import java.util.*;public class Main { static int n; // 노드의 개수 static ArrayList[] list; // 노드 저장 static boolean[] visited; // 방문 여부 체크 stati.. 2024. 8. 14.
[백준] 7578번: 토마토 (Java) 1. 문제설명토마토는 격자 모양 상자의 칸에 하나씩 보관된다. 익은 토마토의 인접한(상하좌우) 곳에 있는 익지 않은 토마토들만 익은 토마토의 영향을 받아 익게 된다. 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 구하는 문제이다.만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력, 토마토가 모두 익지 못하는 상황이면 -1을 출력한다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식⇒ 모든 토마토가 익는 최소 시간을 구하는 문제 → BFS토마토 정보를 담은 `int[][] box`를 사용한다.상하좌우로 이동할 수 있는 배열(dx, dy)을 사용한다.익은 토마토를 큐에 추가한다. (위치 정보)큐가 빌 때까지큐에서 값을 꺼내, 이 위치의 상하좌우를 탐색한다. (`.. 2024. 8. 13.
[백준] 6603번: 로또 (Java) 1. 문제설명1~49의 숫자 중에서 k(k>6)개의 수를 골라 집합S를 만들었을 때, 이 집합S에서 6가지 수를 고르는 경우를 출력하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식⇒ 모든 조합 구하기 (모든 경로 방문) → DFSDFS를 사용해서 가능한 모든 6개의 조합을 생성한다.메서드를 재귀 호출하며, 6개가 선택되면 그 조합을 저장한다.StringBuilder를 사용해 조합을 저장하고, 출력한다. 3. 최종 코드import java.io.*;import java.util.*;public class Main { static int[] arr = new int[6]; // 선택된 조합을 저장할 배열 static int[] nums; // 입력받은 숫자 집합 stat.. 2024. 8. 12.
[백준] 2606번: 바이러스 (Java) 1. 문제설명한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 감염된다. 1번 컴퓨터가 웜 바이러스에 걸렀을 때, 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식⇒ 네트워크 연결 → DFS노드의 수와 간선 정보를 인접행렬로 저장한다.방문 체크할 visited 배열을 생성한다.재귀 호출하는 메서드를 통해 1번과 연결된 컴퓨터를 찾는다.탐색할 노드 번호(row)를 매개변수로 받는다.행렬에서 해당 row를 탐색하며 col이 1이고, 방문하지 않은 경우count 1 증가 (결과값)해당 col로 재귀 호출 3. 최종 코드import java.io.*;public class Main { static int.. 2024. 8. 12.
[백준] 2178번: 미로 탐색 💡문제 분석 요약N x M 크기의 미로에서 (1, 1)에서 (N, M)까지 이동하는데 필요한 최소의 칸 수를 구하는 문제이다.시간 제한: 1초메모리 제한: 192MB 💡알고리즘 설계줄의 개수 N, 칸의 개수 M 를 입력받고, (N, M)의 미로 정보를 입력받는다.BFS 메서드를 호출하여 미로를 탐색한다.BFS 메서드`Queue` 타입의 큐를 생성한다. (탐색할 좌표를 저장함)시작 위치 (1, 1)를 큐에 넣는다.큐가 빌 때까지:큐의 맨 앞의 값을 꺼낸다. ⇒ 현재 위치 (`cur`)`cur`의 상하좌우를 탐색한다.탐색 위치 (x, y)가 미로의 범위에 속하고, 이동 가능한 경로 (`graph[x][y] = 1`)일 경우해당 위치를 큐에 넣는다.해당 위치를 방문 처리한다. (`graph[x][y] = .. 2024. 7. 20.
[백준] 1012번: 유기농 배추 💡문제 분석 요약배추를 심은 배추밭의 정보를 입력받아, 배추가 모여있는 곳이 몇 군데인지(최소의 배추흰지렁이 수) 출력하는 문제이다.시간 제한: 1초메모리 제한: 512MB 💡알고리즘 설계`boolean[][] land` 에 배추가 있는 경우 true, 없는 경우 false로 설정한다.`land` 를 순회하며 배추가 있을 경우해당 위치를 false로 설정하고 `count` 를 증가시킨다.해당 위치로 dfs 메서드를 호출한다.dfs 메서드해당 위치의 상하좌우를 순회하여 배추가 있을 경우해당 위치를 false로 설정한다.해당 위치로 dfs 메서드를 재귀 호출한다. 💡코드import java.io.*;public class Main { static boolean[][] land; static .. 2024. 7. 18.
[백준] 1260번: DFS와 BFS 💡문제 분석 요약입력받은 그래프의 정보를 DFS와 BFS로 탐색한 결과를 출력하는 문제이다.시간 제한: 2초메모리 제한: 128MB 💡알고리즘 설계그래프 정보를 인접 행렬로 저장한다.DFS 구현재귀 함수를 이용한다.방문한 노드를 visited = true(방문 체크)로 설정하고 StringBuilder에 저장한다.해당 노드와 인접한 노드 중 방문하지 않은 노드(visited == false)를 재귀 호출한다.BFS 구현큐를 이용한다.시작 노드를 큐에 넣고 visited = true 로 설정한다.큐가 빌 때까지 다음을 반복한다.큐에서 맨 앞 노드를 꺼내고, StringBuilder에 저장한다.꺼낸 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 넣고 visited = true 로 설정한다. 💡코드i.. 2024. 7. 16.
반응형