티끌모아 태산

가장 처음에 든 생각은1,1부터 시작해서 n,m 좌표까지 탐색하며 테트로미노를 하나씩 놔보는 것이다.이 때, 가능한 테트로미노의 경우는 모두 사전에 정의해야한다.I-모양 (회전 시 두 가지 형태)O-모양 (회전해도 동일)T-모양 (회전 시 네 가지 형태)S-모양 (회전 시 두 가지 형태)Z-모양 (회전 시 두 가지 형태)L-모양 및 대칭된 J-모양 (회전 및 대칭 시 여덟 가지 형태) 그 코드는 아래와 같다.import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.io.IOException;import java.ut..

BFS 알고리즘을 이용해서 D, S, L, R연산을 반복하며 a가 b가될 때 까지 최소 경로를 찾으면 될 것같다. 평소에 풀던 BFS알고리즘 문제와 두 가지 다른 점이 있어서 고민을 했다.visited 처리를 어떻게 해아하는가평소에는 연산 횟수를 출력하면 됐지만, 이 문제는 어떤 연산을 했는지 연산 순서를 출력해야함 먼저 1번 이슈는 vistied 배열을 사용했다.0~9999까지 숫자가 결과로 나오므로, 연산 결과가 b가 아닌 0~9999사이 숫자는 다시 연산할 필요가 없다즉 visited[9999] 배열을 선언하여, 해당 숫자를 방문처리하면 된다. 2번 이슈는 Queue에 삽입하는 값을 단순 Integer가 아닌, 사용자 정의 클래스를 만들어서 해결했다.아래 두 정보를 저장하는 사용자 정의 클래스이다...

문제를 보자마자 처음에는 우선순위 큐를 이용해야겠다고 생각했다.1. 우선순위큐 선언2. I 연산시 단순 우선순위큐 삽입3. D연산시 -1이면 현재 큐의 우선순위를 뒤집어서 사용하지만 위 방법을 사용시 3번이 문제가 된다.자바에서는... 이미 사용하고있는 우선순위 큐의 우선순위 정의를 다르게 하는 메소드도 없을 뿐더러,직접 정의한다면 새로운 우선순위큐를 만들어서 옮겨 넣는 방법 뿐이다.D 연산 때 마다 이렇게하면 Timeout이 발생할 것이다.그래서 다음 방법으로는 Deque를 이용해야겠다고 생각했다.1. Deque선언2. D연산시, 1이면 앞에서부터 제거, -1이면 뒤에서부터 제거3. I연산시 단순 삽입 후, 크기순으로 정렬하지만 위 방법 역시 3번이 문제가 된다.Deque역시 정렬하는 방법이 까다롭다...

그래프가 주어지고, 최소 값을 찾아야 하므로 전형적인 BFS 알고리즘 문제이다.주의사항1) BFS에 사용할 큐를 미리 선언하여, 입력 받을 때 토마토의 위치를 큐에 저장한다. 2) 큐의 사이즈가 계속 변하므로, q.size()를 직접 사용하지 않고 size = q.size()의 size변수를 이용해야한다.3) ripend 변수를 사용하여 토마토가 익었는지 체크한다.4) BFS탐색 완료 후, 배열을 검사하며 0이 있는지 (안익은 토마토)를 검사한다.import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.Li..

그래프가 주어지고. 최단경로를 찾아야하는 문제이므로 BFS 알고리즘을 사용한다.10x10 모양의 보드라고 했지만 100칸 짜리 배열이라고 생각하면 편하다.배열의 각 칸이 다음 몇번째 칸으로 이동하는지 저장해놓는다.최소 거리를 구해야 하므로 visited배열을 이용해서 방문하지 않은 칸만 방문할 수 있도록 한다.단, vistied배열에 주사위 굴린 횟수를 저장, 값이 0인 배열이 index가 방문하지 않은 칸이다.import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.LinkedList;import java..

그래프가 주어졌고 탐색을 해야하므로 dfs나 bfs를 사용해야하는 문제이다.최단경로 또는 특정한 목표지점이 있는 것이 아니고, 모든 그래프를 탐색해야하기 때문에 어떤 방식을 사용해도 상관 없다.나는 편의상 익숙한 dfs를 사용했다.적록색약인지 아닌지 구분하는 플래그 isColorWeakness 변수를 선언했고,이 플래그가 true일 때 그래프 전체 탐색, false일 때 그래프 전체 탐색하여 총 두번의 전체 탐색을 했다.기본적으로 다음 탐색 지점이 같은 컬러일 때 탐색하도록 했지만적록색약일 때는 현재 컬러가 R 또는 G인지 검사하고, 다음 컬러도 R 또는 G인지 검사해서 같으면 탐색하도록 했다.시간초과가 뜰 줄 알았는데 시간안에 클리어 됐다.이게 왜 되지....?import java.io.Buffered..

좌표 그래프가 주어지고, 최소 일수를 찾아라?BFS문제이다.그런데 평소와 다른 점이 있다면 2차원 그래프가 아니라, 3차원 이라는 것이다.x,y,z좌표가 헷갈리지 않도록 유의하면서 풀면 2차원과 크게 다르지 않다.import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int m, n, h; static int[][][] tomat..

실패한 코드.Queue를 사용하여 정수 배열을 입력받았고,명령이 R이면 Stack을 이용해서 Queue를 뒤집었다.그 결과, 시간 초과가 떴다.import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.LinkedList;import java.util.Queue;import java.util.Stack;public class Main { static Queue queue = null; public static void main(String[] args) thro..