백준 알고리즘(BOJ)(46)
-
BOJ_1600_ 말이 되고픈 원숭이
1. 구분: 그래프 이론, 그래프 탐색, 너비 우선 탐색 언어: Java 전략: 원숭이가 스킬을 쓴 횟수 만다 다른 상태를 가진다. --> 다른 상태 배열을 만들어야 한다. 가장 최소로 이동하고 싶으니 우선적으로 말처럼 이동하는 것을 다 쓰도록 한다. 말 스킬을 다 쓰면 이제 한 칸씩 이동한다. 2. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static class Node{ //x,y 좌표와 이동 횟수를 나타내는 level, 말처럼 뛴 횟수를 나타내는 breakn int x, y, level, breakn; Node(int y, int x, int level, in..
2021.09.17 -
BOJ_2178_미로 탐색
1 구분: 그래프 이론, 그래프 탐색, BFS 언어: Java 전략: BFS 풀어야 하는 이유 - 최단 거리를 구해야 하는데 DFS는 깊게 탐색하니까 비효율적이다. 시간 초과 방법1 - 내가 다녀온 곳들을 1씩 증가 - 최종 도착지에 도달했을 때의 그 숫자가 정답 방법 2 - 내가 방문한 곳들을 확인하는 boolean 배열이용해서 방문여부 확인. 큐에 좌표와 level도 함께 넣는다. 인접한 곳에 level을 1씩 증가한다. 2. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import..
2021.09.17 -
BOJ_17086_아기 상어2
1 구분: 그래프 이론, 그래프 탐색, BFS, DFS 언어: Java 전략: 상어와 그 주변(8방)을 BFS를 통해 탐색하면서, 그 값을 갱신한다. 어떤 지점의 안전거리는 나를 부른(내 주변, 나를 인접해하는) 것보다 1 크다 -> 나를 부른 것의 값+1 상어가 있는 자리를 -1로 처음 설정하여 +1 할 때, 진짜 값과 상어의 값의 혼란을 줄인다. 최대 값을 매번 갱신한다. 현 최대 값과, 새로 갱신되는 map의 값을 비교한다. 2. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { //배열의 x,y좌표를 담는 class 생성 static class Node{ int y;..
2021.09.15 -
BOJ_2644_촌수계산
1. 구분: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 언어: Java 전략 각 촌수의 연결 관계를 그래프로 보고, 이를 배열에 저장 - 연결되어있으면 true, 아니면 false(default) BFS로 그래프를 탐색 촌수가 1씩 증가하는 것은, 나에게서 인접한 것들이다. 따라서 나와 인접한 것을 큐에 삽입할 때, 내 번호와 촌수를 함께 넣는다. 2. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static class Node{ //q에 넣을 사람번호와 start기준 촌수 int item; int level; Node(int item, int le..
2021.09.15 -
BOJ_2529_부등호
1 구분: Brute-force 언어: Java 전략: 순열을 이용해 부등호에 넣은 숫자 조합을 생성한다. 순열이 생성되면 부등호 조건에 맞는지를 확인한다. 조건에 맞는 순열을 숫자로 만들어 최대, 최소값을 구한다. 출력할 때에는 문자열로 변경한다. - 이때, 0이 생략된 숫자를 문자로 변경할때, 0을 추가한다. 2. 코드 import java.util.Scanner; public class Main { static int k; //부등호의 전체 개수 static String[] boo; //부등호를 담을 string배열 static int[] comb, num; //순서를 가진 숫자 조합배열, 0~9까지의 숫자배열 static boolean[] check; //num의 사용여부를 가릴 boolean 배..
2021.09.08 -
BOJ_16968_차량 번호판1
1 구분: brute-force 언어: java 전략: 코드를 짠다고 생각하지 말고, 수학 문제를 푼다고 생각해보자 숫자는 10가지, 문자는 26가지가 있다. **** - 각 자리에 들어갈 수 있는 문자나 숫자는 내 바로 앞것과 같지만 않으면 된다 --> 즉, 내 앞꺼랑만 다르면 된다 따라서 내 앞이 숫자면, 그 다음에는 그것만 아니면 되고(9가지), 문자이어도 동일하다(25)가지 내 앞의 것을 살피고, 단 한개와만 같지 않게 구한다. 2. 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scan..
2021.09.07