Java

문제 접근 방식 기존 BFS를 이용한 문제들과 똑같은 방법으로 풀면 되는 문제지만 이동 방향이 앞뒤양옆이 아닌 나이트가 이동할 수 있는 8가지의 방향을 탐색해주면 된다. int[] knightX = {2, 2, 1, 1, -1, -1, -2, -2}; int[] knightY = {1, -1, 2, -2, 2, -2, 1, -1}; 위와 같이 나이트의 이동 방법을 배열에 기록해두면 편하다. 이제 저 배열을 순회하면서 현재 위치부터 BFS를 이용해 탐색을 하면 되고 이동한 위치가 목표 지점과 같은 경우에는 이동 횟수를 기록하고 탐색을 종료해주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { Buff..

문제 접근 방식 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 위 문제에 위, 아래층 탐색이 추가된 문제로 기존에는 2차원 배열의 토마토 상자의 앞뒤양옆의 익지 않은 토마토들을 하루마다 익어가게 만들었다면 이번에는 앞뒤양옆 + 상하를 하루마다 익어가게 해주면 된다. 문제의 푸는 방법은 같지만 2차원 배열에서 3차원 배열로 바뀐만큼 기존 방식에 약간의 변화를 줘야 한다. private static class XYZ { private int z; private int x; private int ..

문제 접근 방식 일단 문제를 간단하게 정리부터 해보겠다. S는 이다'솜'파이고 Y는 임도'연'파이다. 5 * 5 형태로 25명의 학생이 앉아 있을 때 7명을 골라야 한다. 7명의 자리는 가로나 세로로 반드시 인접해 있어야 한다. = 상하좌우 중 한 칸 인접해야 함 7명 중 4명은 이다솜 파여야 한다. 2번 항목에서는 25명 중 7명을 고르는 조합을 구해야 하는 것을 알 수 있고 3번 항목에서는 고른 7명이 인접한 지 상하좌우로 탐색해야 하는 것을 알 수 있다. 그래서 이번 문제는 백트래킹과 BFS를 이용해서 풀 수 있기에 백트래킹으로 7명의 조합을 구하고 BFS로 이들이 인접해 있는지 확인하면 된다. 우선 7명의 조합을 구하는 과정은 중복 없이 구하기 위해 이미 사용한 자리는 다시 사용하지 않게 해야하고..

문제 접근 방식 굉장히 오래 걸려서 푼 문제인데 풀고 나니 쓸데없는 곳에서 시간 낭비를 많이 한 문제 같다. 우선 계란끼리 서로 부딪혔을 때 내구도가 0 이하로 떨어진다면 해당 계란은 깨진 계란이라고 기록을 남겨주고 각 계란들의 내구도를 갱신해 준다. 계란의 내구도는 자신의 내구도 - 부딪힌 상대 계란의 무게로 계란 객체 배열이나 정수형 배열로 부딪힌 후의 내구도를 갱신해 주면 된다. 처음에는 가장 왼쪽에 있는, 즉 배열의 0번째 인덱스 (now)의 계란을 손에 쥐고 깨지지 않은 계란을 아무거나 하나 골라 둘을 부딪히게 한다. 그 후 계란을 모두 내려놓고 방금 집었던 계란의 오른쪽 한 칸 (now + 1)의 계란을 손에 쥐고 다시 깨지지 않은 계란을 아무거나 하나 골라 부딪히게 하는 것을 반복해 주면 된..

문제 접근 방식 주어진 수들에서 중복 없이 6개씩 고르는 경우를 출력하는 문제로 순서가 달라도 같은 경우로 취급하는 것만 생각하면서 문제를 풀면 된다. N과 M 시리즈 문제에서 많이 풀어본 유형이기 때문에 모두 풀어본 사람이라면 쉽게 풀 수 있는 문제다. 수의 사용 여부를 기록하지 않고 순서만 다른 결과도 제외하기 위해서는 그냥 재귀 호출 시마다 반복문의 시작 인덱스를 1씩 증가시켜 주면 된다. 풀이 public class Main { private static StringBuilder sb; private static int n; private static int[] arr; private static int[] lottoNumbers = new int[6]; public static void main..

문제 접근 방식 주어진 수들로 부분수열을 만들어 합이 S가 되는 경우에 카운트를 1씩 늘려주면 된다. N과 M 시리즈 문제들과 비슷하게 풀면서 카운팅만 해주면 되는데 조심해야 할 부분은 [-3, -2, 5], [-3, 5, -2], [-2, -3, 5], [-2, 5, 3] 같이 똑같은 수가 들어가고 순서만 다른 경우는 모두 하나의 수열로 취급해야 한다. 이제 재귀를 통해 수열을 만들어주면서 수의 합이 S인 경우 카운팅을 해주면 되고 재귀의 기저조건은 만들어진 수열의 크기가 N과 같은 경우지만 1 ~ N까지의 수열의 크기를 만들 때마다 sum이 S와 같은지 확인해줘야 한다. 풀이 public class Main { private static int n; private static int s; privat..

문제 접근 방식 N * N 크기의 체스판에 N개의 퀸들이 서로 공격하지 않게 놓으려면 우선 퀸의 공격 범위를 알아야 한다. 퀸은 가로와 세로의 직선과 대각선 모두 자신이 이동하고 싶은 만큼 이동할 수 있는데 이 말은 퀸과 같은 행이나 열 혹은 같은 좌표의 기울기를 가진 대각선을 제외한 곳에만 퀸을 둘 수 있다는 것이다. N과 M시리즈를 풀면서 많이 사용했던 사용 여부를 기록하던 배열 방법을 사용해서 풀면 생각보다 쉽게 풀 수 있다. 우선 위와 같이 퀸이 하나 존재 한다면 같은 행과 열에는 다른 퀸을 둘 수가 없으니 한 줄에는 하나의 퀸만 둘 수 있고 모든 줄에 퀸이 존재한다면 모든 퀸들이 서로 공격 하지 못하는 위치에 존재하게 되니 이를 재귀 함수의 기저 조건으로 지정해 주면 된다. (X == N) 다음..

문제 접근 방식 11번 문제에 조건 하나만 더 추가된 문제로 다음 인덱스를 뽑을 때마다 이전 인덱스 이전의 값을 제외한 동일한 인덱스 부터의 값만 뽑을 수 있다. 재귀 호출 시 두 번째 인자로 넘겨주던 시작 인덱스 값을 현재 호출 스택에서 사용 중인 시작 인덱스를 넘겨주면 된다. 풀이 public class Main { private static StringBuilder sb = new StringBuilder(); private static int n; private static int m; private static int[] arr; private static int[] sequence; public static void main(String[] args) throws IOException { Bu..