문제 링크 1. 기본적인 그래프 문제였지만 요즘 문제 풀기가 너무 싫어서 뭉그적거리면서 풀었던 문제 2. BFS를 이용하여 문제를 해결하였다. 나이트가 이동할 수 있는 8가지 방향을 배열로 만들어준다. int[] dx = { 1, 2, 2, 1, -1, -2, -2, -1 }; int[] dy = { -2, -1, 1, 2, 2, 1, -1, -2 }; 조건에 맞으면 queue에 넣는데, 중요한 점은 cnt 2차원 배열을 만들어 해당 위치까지 몇 번을 이동했는지를 저장한다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n; static Pos now..
그래프
문제 링크 1. 골드 5 문제로 분류되어있던데, 그 정도 난이도는 아닌 것 같다. 정답률도 $58\%$로 다소 높은 편. 여느 문제와 비슷하여 쉽게 풀었다. 다만 조금 더럽게 푼 듯하다. 2. flag 변수를 이용해 적록색맹 일 때 아닐 때를 구분하여 if 문 처리를 하였다. 아스키코드 값을 통해 'R' - 'G' = 11 임을 이용하였다. 다른 사람의 풀이를 보니 적을 녹으로 바꿔서 bfs 한 번 더 돌리던데 그게 좀 더 깔끔한 코드인 것 같다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n; static char[][] data; public ..
문제 링크 1. 이전에 풀었던 토마토 문제의 응용문제이다. 2차원 배열이었다면 이번에는 3차원 배열.. 3차원 배열을 너무 오랜만에 써서 맨 앞의 인덱스가 행이었나 면이었나 기억이 안 났다. 또 모두 익을 때까지 며칠이 걸리는지 카운트하는 부분에서 살짝 헤맸다. 2. BFS로 풀었다. dx, dy, dz 배열로 이동할 6가지 방향(상, 하, 좌, 우, 앞, 뒤)을 잡아준다. 1. 배열 전체를 순회하며 익은 토마토가 있는 부분을 queue에 넣는다. 2. queue가 empty일 때까지 다음을 반복한다. 2-1. queue에서 원소를 하나씩 빼서 6가지 방향에 대하여 2-2. 해당 방향에 익지 않은 토마토가 있다면 익게 하고 queue에 넣는다. 단, 익게 할 때 단순히 1로 바꾸는 것이 아니라 이동하기 ..
문제 링크 1. 지나왔던 알파벳인지 파악하는 부분에서 조금 헤맸던 문제. list를 사용하여 전체 순회를 하게 할 수도 있지만, 시간 효율성이 떨어진다. visited 배열을 이용하여 풀면 효율적이다. 2. 이동 거리의 최대값을 찾아야 하므로 백트래킹을 써야 한다. 그렇기 때문에 DFS를 사용하는 것이 효과적이다. visited 배열은 boolean[26] 배열로 해당 알파벳 - 'A'를 한 인덱스를 이용하면 된다. 나머지는 코드를 보면 이해가 될 것이다. 3. import java.util.Scanner; public class Main { static int answer = 0, r, c; static char[][] data; static boolean[] visited = new boolean[2..
문제 링크 1. 입력 데이터를 어떻게 처리할지에 대한 고민을 조금 했던 문제이다. 데이터 배열을 만들고 난 후에는 단지번호붙이기 문제와 유사해 쉽게 풀 수 있다. 2. 직사각형의 왼쪽 아래 꼭짓점의 $(x, y)$과 오른쪽 위 꼭짓점의 $(x, y)$가 주어진다. 일단 노트에다가 이를 고려해 찍어보았다. 문제는 이 좌표계를 배열화 시켜야 하는 것인데, 고민해보면 다음과 같은 규칙을 찾을 수 있다. $(2, 0)$ ~ $(4, 4)$ 이라면, data[0][2] ~ data[3][3] $(1, 1)$ ~ $(2, 5)$ 이라면, data[1][1] ~ data[4][1] $(4, 0)$ ~ $(6, 2)$ 이라면, data[4][0] ~ data[1][5] 배열 모양은 좌표계를 x축을 기준으로 대칭시킨 모..
문제 링크 1. 다익스트라 알고리즘. 처음 접해보는 알고리즘이다. 유튜브 영상과 해답을 보며 공부하였다. 자료구조 시험칠 때 친구랑 얘기하다가 다익스트라 관련 얘기가 나왔었는데, 나는 그게 뭐냐고 안 배웠다고 하고 친구는 그걸 왜 모르냐고 중요한 건데 했던 웃픈 사연이 있는 알고리즘이다. 우리 교수님은 안 알려주셨는데 다른 교수님 수업에서는 가르쳐줬다고 한다. 중요한 알고리즘이다. 흔히 우리 주변에서 접할 수 있는 지도의 최단 경로를 구할 때도 이 알고리즘이 적용된다. 오늘 배우긴했지만 또 복습하자. 2. 그래프를 인접 행렬로 구성하면 안 된다. 문제의 조건 범위가 $0\leq V\leq20000$ 인데, 인접 행렬로 구성하게 되면 $20000\times20000=$ 대략 4억으로 메모리 초과가 난다. ..
문제 링크 1. 이전에 풀었던 기본적인 그래프 문제. 항상 BFS로만 풀어와서 이번에는 DFS로 풀어보았다. DFS가 좀 더 직관적인 것 같다. 2. 1. 가장 큰 높이 $h$ 부터 가장 낮은 $1$ 까지 높이를 하나씩 낮춰주며 기준을 잡는다. 2. 기준 높이 $h$ 보다 큰 영역은 물에 잠기지 않으므로 그러한 영역의 개수를 구한다. 3. 영역의 개수의 최대값을 출력한다. 이하 코드 참고 3. import java.util.Scanner; public class Main { static int[][] area; static int n; public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); ..
문제 링크 1. 많이 풀어 봤던 기본적인 그래프 문제. 유기농 배추 문제와 매우 유사해서 쉽게 풀었다. 테스트 케이스는 다 맞고, 전혀 틀린 부분이 없는데 오답처리가 나길래 골치가 아팠다. 원인은 내가 잠시 수정했던 범위였는데 이런 어이없는 실수는 하지 않도록 주의하자. 2. 풀이는 유기농 배추 문제를 참고하면 될 것 같다. (링크 걸어 놓았음) 단, 이 문제에서는 4 방향이 아닌 8 방향을 모두 검사하여야 한다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int w, h; static int[][] area; public static void main(..
