Algorithm
[백준] 11403 경로 찾기 - Java
[백준] 11403 경로 찾기 - Java
2022.05.27행렬 형태로 주어진 그래프를 이용해 탐색을 수행해야 한다. 행에 대해서 bfs를 돌린 후 해당하는 행이 접근할 수 있는 열을 기록하고 출력한다. 주어진 조건에서 i,i에 해당하는 좌표는 무조건 0으로 주어진다고 했으니, visit를 체크할 때 주의하자. import java.util.*; import java.io.*; public class Main { static int N; static int[][] map; static boolean[] visit; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..
[백준] 3184 양 - Java
[백준] 3184 양 - Java
2022.05.27영역에 속한 양과 늑대의 수를 비교해 연산을 수행해야 한다. 영역을 구할 때는 dfs를 돌려서 구할 수 있다. 매 시행마다 영역 안에 있는 양의 수와 늑대의 수를 초기화 해야 됨을 잊지 말자. import java.util.*; import java.io.*; public class Main { static int N; static int M; static char map[][]; static boolean[][] visit; static int cnt; static int[][] dir = {{1,0}, {-1,0}, {0,-1}, {0,1}}; static int wolf_cnt = 0; static int sheep_cnt = 0; static int wolf_ans = 0; static int s..
[백준] 4963 섬의 개수 - Java
[백준] 4963 섬의 개수 - Java
2022.05.27지난번에 풀었던 유기농 배추와 유사한 문제이다. 매 테스트케이스마다 지도와 방문 여부, 정답 변수를 초기화 해 주고 dfs를 돌려 탐색하자. import java.util.*; import java.io.*; public class Main { static int N; static int M; static int map[][]; static boolean[][] visit; static int cnt; static int[][] dir = {{1,0}, {-1,0}, {0,-1}, {0,1}, {1,1}, {1,-1}, {-1,1}, {-1,-1}}; public static void main(String[] args) throws IOException { BufferedReader br = new Bu..
[백준] 1012 유기농 배추 - Java
[백준] 1012 유기농 배추 - Java
2022.05.27배추가 심어진 밭을 이차원 배열로 표현하고, 그 배열을 그래프로 표현해 풀 수 있는 문제이다. dfs와 bfs 모두 사용할 수 있다. 이번에는 재귀를 통한 dfs를 사용해 풀어보자. import java.util.*; import java.io.*; public class Main { static int N; static int M; static int K; static int[][] map; static boolean[][] visit; static int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}}; static int cnt; public static void main(String[] args) throws IOException { BufferedReader br = n..
[백준] 3055 탈출 - Java
[백준] 3055 탈출 - Java
2022.05.27물이 전이되는 조건 때문에 처리해줘야 하는 요소가 많다. 일단 최단시간을 구하는게 목적이니, bfs를 돌리면서 최단 시간을 갱신하면 풀 수 있을 것 같다. 고슴도치는 물이 전이된 곳에 갈 수 없으니 물에 대한 bfs를 먼저 돌려 언제 물이 해당 위치에 전이되는지 기록하자. 그 후는 항상 하던대로 고슴도치에 대한 bfs를 수행하면 된다. import java.util.*; import java.io.*; public class Main { static int N; static int M; static char[][] map; static int[][] dist_water; static int[][] dist_hedgehog; static boolean[][] visit; static int[][] dir ..
[백준] 1697 숨바꼭질 - Java
[백준] 1697 숨바꼭질 - Java
2022.05.27최소 시간을 구하라고 했으니.. bfs를 사용해 dist를 갱신하고 최소 시간을 출력하면 될 것 같다. 기존 문제는 격자 혹은 그래프를 대놓고 줘서 그래프를 어떻게 구성해야 할 지 쉽게 떠올릴 수 있었는데, 이번 문제에서는 그래프에 대한 단서가 별로 없다. 먼저 그래프를 디자인해보자. 정점은 술래가 위치한 상태 / 간선은 +1. -1. *2 세 가지로 구성할 수 있겠다. 위의 조건에 맞춰 그래프를 구성하고 bfs를 돌려 답을 구하자. import java.util.*; import java.io.*; public class Main { static int N; static int K; static int[] dist; static boolean[] visit; public static void main(..
[백준] 7562 나이트의 이동 - Java
[백준] 7562 나이트의 이동 - Java
2022.05.27bfs로 격자를 순회하면서 거리를 갱신해 풀 수 있는 문제다. 관련 문제를 많이 풀어서 그래프 유형에 익숙해지자. import java.util.*; import java.io.*; public class Main { static int I; static int ans; static int[][] map; static boolean[][] visit; static int[][] dist; static int[][] dir = {{2,-1}, {2,1}, {1,-2}, {1,2}, {-2,-1}, {-2,1}, {-1,-2}, {-1,2}}; public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..
[백준] 14502 연구소 - Java
[백준] 14502 연구소 - Java
2022.05.261. 벽을 설치할 수 있는 위치 탐색 2. 벽을 설치하는 모든 경우를 고려해야 한다. dfs로 벽을 설치하고 설치가 완료됐으면 bfs로 바이러스의 수를 기록한다. import java.util.*; import java.util.concurrent.LinkedBlockingDeque; import java.io.*; public class Main { static int N; static int M; static int wall; static int ans; static int[][] map; static boolean[][] visit; static int[][] able_wall; static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; public sta..
[백준] 13904 과제 - Java
[백준] 13904 과제 - Java
2022.05.23그리디와 우선순위 큐 자료구조를 사용해 풀 수 있다. 우선순위 큐는 그냥 쓰면 되는데.. 그리디는 어떻게 사용해야 할까? 일단 객체 하나 만들고 점수 내림차순으로 정렬하자. 그 후 계산을 시작한다. 하루에 과제 하나를 끝낼 수 있으니, 기간이 많이 남은 과제는 최대한 나중에 하면 된다. 점수에 대해 정렬이 된 상태라서, 이렇게 작성하면 고득점을 얻을 수 있다. import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int..
[백준] 16987 계란으로 계란치기 - Java
[백준] 16987 계란으로 계란치기 - Java
2022.05.23백트래킹으로 모든 경우를 계산해 풀 수 있는 문제이다. (브루트포스 느낌) 재귀는 반복문으로 구현할 수 있고 반복문은 재귀로 구현할 수 있듯, 이 문제도 반복문을 사용해 풀 수 있을 것 같긴 하다. 재귀적 구조에 익숙해져야겠다. 아직은 너무 어색하다. import java.util.*; import java.io.*; public class Main { static int N = 0; static int cnt = 0; static Egg[] egg; static int max = 0; public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..
[백준] 1759 암호 만들기 - Java
[백준] 1759 암호 만들기 - Java
2022.05.23백트래킹으로 풀 수 있는 문제이다. 조건은, 모음이 1개 이상 / 자음이 2개 이상이다. 암호의 문자는 하나씩밖에 사용할 수 없으니 백트래킹 함수는 인자를 두 개 받도록 설정해 처리해주자. 값의 후보가 되는 요소들은 리스트로 담아서 풀 수 있는데, 이번에는 배열을 사용해서 풀어보자. arr의 값이 cand의 인덱스로 접근해서 답을 출력한다. import java.util.*; import java.io.*; public class Main { static int L, C = 0; static int[] arr; static char[] cand; public static void main(String args[]) throws IOException { BufferedReader br = new Buffe..
[백준] 2448 별찍기 11 - Java
[백준] 2448 별찍기 11 - Java
2022.05.21재귀 문제임을 파악하자. 일단 주어진 예시를 잘라서 재귀의 basis를 구한 후 접근해야 한다. N = 3 * 2^k 이므로, 이차원 배열의 행 : 3 * 2^k 이차원 배열의 열 : 3 * 2^(k+1) 위의 식을 기억하고 점화식을 작성한 후 코드를 작성하자. import java.util.*; import java.io.*; public class Main { static int N; static char[][] map; static char[][] basis = {{' ',' ','*',' ',' '}, {' ', '*', ' ','*', ' '}, {'*','*','*','*','*'}}; public static void main(String args[]) throws IOException { ..