Melody Coding

Gold V문제(출처: https://www.acmicpc.net/problem/16509) 문제 풀이bfs를 활용하여 상하좌우로 이동 후 대각선으로 이동할 때 조건을 설정해 준다. 1. 장기판 범위 안인지 확인2. 대각선으로 이동하는 길에 다른 기물이 있는지 확인3. 방문 여부 확인4. 왕의 위치인지 확인 위와 같이 4가지의 조건을 설정해 주면 문제를 해결할 수 있었다.   my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringToke..

Gold V문제(출처: https://www.acmicpc.net/problem/14217) 문제 풀이 1. 각 도시 -> 수도로 탐색하는 방법: 시간초과는 발생하지 않았지만 시간이 오래 걸리는 것을 확인할 수 있었다. 2. 수도 -> 각 도시 탐색하는 방법: bfs를 한 번만 호출하여 답을 얻을 수 있어 1번보다 시간이 적게 걸리는 것을 확인할 수 있었다. 위와 같은 방법 말고는 단순 bfs를 활용하면 문제를 해결할 수 있었다.   my solution (Java)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io...

Gold III문제(출처: https://www.acmicpc.net/problem/1937) 문제 풀이 처음에 dfs만 활용하여 문제를 해결하려고 했었다. 하지만 시간 초과가 발생했고 dp도 함께 사용해야 한다는 것을 알게 되었다. 이미 dfs 탐색을 통해 값을 구했다면 배열에 저장해 두고 다시 탐색을 하지 않도록 구현하여 시간을 줄이는 방법을 택하였다.    - my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int arr[][], dp[][], n, ..

Gold III문제(출처: https://www.acmicpc.net/problem/16954) 문제 풀이 이 문제는 벽이 1초마다 아래로 한 칸씩 내려간다는 부분이 중요하다.1초마다 아래로 한 칸씩 움직이는 부분을 실제로 배열에 저장하지 않고 인덱스로 접근하여 이동할 위치가 빈칸인지 벽인지 확인한다.- 자세한 풀이는 다음에 시간이 날 때 작성   - my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class _16954_ { // 움직이는 미로 탈출 stat..

Gold IV문제(출처: https://www.acmicpc.net/problem/2665) 문제 풀이 bfs를 활용하여 모든 방을 탐색한다. 흰 방이면 바꾸어야 할 최소의 수를 전 값으로 그대로 유지하고 검은 방인 경우에는 바꾸어야 할 최소의 수를 전 값 +1로 바꿔준다. 이때 최소의 수를 구하기 위해 조건을 잘 설정한다.   - my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class _2665_ { // 미로만들기 static boolean arr[][..

Gold V문제(출처: https://www.acmicpc.net/problem/27211) 문제 풀이 비어있는 곳에서 상하좌우를 탐색하여 비어있는 곳을 찾아 이동한다.범위 밖으로 이동할 때는 이어진 곳을 잘 생각하여 이동한다.   - my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class _27211_ { // 도넛 행성 static int arr[][], result, n, m; static b..

Gold IV문제(출처: https://www.acmicpc.net/problem/1261) 문제 풀이 bfs를 활용하여 벽을 몇 개 부수어야 하는지를 세어준다.   - my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class _1261_ { // 알고스팟 static int arr[][], m, n, result; static int visited[][]; static int dx[] = { -1,..

Gold IV문제(출처: https://www.acmicpc.net/problem/16469) 문제 풀이 악당의 각 위치부터 시작해서 상하좌우로 움직여 각 지점마다 최소 시간을 구해둔다. 그 후에 전체를 탐색하여 3명 다 방문한 곳이며 시간이 최소인 시간을 구한다.    - my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class _16469_ { // 소년 점프 static int arr[][], ..

Gold V문제(출처: https://www.acmicpc.net/problem/22352) 문제 풀이 백신을 놓기 전과 놓은 뒤의 촬영 결과가 다른 곳을 먼저 찾아 배열에 저장해 둡니다. 그 후에 변화한 값을 기준으로 bfs를 활용하여 항체가 퍼진 곳인지 찾아 줍니다.bfs로 주변을 다 탐색한 후에도 변화한 값이 존재한다면 맞은 백신이 CPCU-1202가 아니므로 "NO"를 출력하고,다 탐색한 후에 변화한 값이 존재하지 않는다면 "YES"를 출력해 줍니다.    - my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedLis..

Gold V문제(출처: https://www.acmicpc.net/problem/13549) 문제 풀이 bfs를 활용하여 가장 빠른 시간을 구하였다.   - my solution (Java)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class _13549_ { // 숨바꼭질 3 public static void main(String[] args) throws IOException { ..