깊이우선탐색5 [백준] 13265 색칠하기 (Java) [13265 색칠하기] 난이도: 골드5 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 문제 입력 출력 [아이디어] 먼저 동그라미들을 노드로 갖고 연결된 직선을 엣지로 생각해주었다. 그 후 노드에 대해 DFS를 사용하여 연결된 노드 두개가 같은 색이라면 impossible, 아니라면 possible을 출력하도록 하였다. [JAVA 코드] import java.io.*; import java.util.*; public class BJ_G5_13265_색칠하기 { static BufferedReader br = new BufferedR.. 2022. 5. 29. [백준] 15681 트리와 쿼리 (Java) [15681 트리와 쿼리] 난이도: 골드5 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 입력 출력 [아이디어] 처음에는 트리를 생성해준 뒤 쿼리 개수만큼 정점의 수를 구했는데, 시간 초과가 났다. 그래서 문제 아래 있는 힌트대로 정점의 개수를 구하는 함수를 구현해주었다. [JAVA 코드] import java.io.*; import java.util.*; public class Main { static BufferedReader br = n.. 2022. 5. 20. [백준] 1520 내리막 길 (Java) [1520 내리막 길] 난이도: 골드4 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 입력 출력 [아이디어] 처음에는 일반 DFS로 풀었다가 시간 초과가 났다. (다시 생각해보니 대략 500 * 500 * 500 * 500 * 4 정도의 시간이 걸리므로 시간 초과가 나는 것은 당연했다.) 시간 초과가 났기 때문에 DP로 풀어야 하나는 것은 알아챘지만 어떻게 DP를 적용해야 하는지 모르겠어서 구글링을 해봤다. 이 분이 설명을 위해 만들어 놓은 애니메이션으로 접근 방법을 알아 차릴 수 있었다. [백준][.. 2022. 4. 4. [SWEA] 1767 프로세서 연결하기 (Java) [1767 프로세서 연결하기] 난이도: SW Test 샘플문제 문제 출처 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [아이디어] 완전 탐색을 사용하였다. 우선 모든 코어들의 위치를 저장해 놓는 List를 만들고, 벽에 붙어있는 코어를 제외한 모든 코어들을 넣어주었다. 그 후 dfs를 사용하여 코어를 사방탐색하였다. 이 때, 코어 연결 상태를 관리하는 것이 중요한데 나는 boolean 이차원 배열을 사용하였다. 해당 방향으로 연결을 하다가 실패하면 연결하던 상태를 지워줘야하는데, 이 방법이 좀 까다로워서 나는 temp라는 boolean 이차원 배열을 새로 만들어 현재 연결 상태를 따로 관리해주었다. 실행 시.. 2022. 4. 4. [백준] 1202 유기농 배추 (Java) [1012 유기농배추] 난이도: 실버2 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 입력 출력 [아이디어] 배추밭을 완전 탐색한다. 배추가 심어져 있는 위치에서 BFS를 사용하여 서로 인접해있는 배추를 체크한다. 몇 개의 배추 더미가 있는지 세어준다. [JAVA 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.. 2022. 3. 3. 이전 1 다음
