Java/Algorithms

문제 접근 방식 정말 x 9999 어렵게 풀었다... 시간초과가 테스트케이스의 1%, 32% 83%에서 발생해서 해결하느라 애먹었다 문제 분류를 살펴보면 DFS지만 BFS가 아직은 더 편해서 BFS를 사용해서 풀었는데 우선 문제를 이해부터 하고 시작하겠다. 사이클을 찾아서 사이클이 존재하지 않는 경우가 몇 개인지 찾는 문제로 1 2 3 4 5 6 7 3 1 3 7 3 4 6 위 예제의 경우에는 3번은 자기 자신으로 바로 돌아와서 혼자 팀을 하는 사이클이 존재하고 4, 6, 7번은 4 > 7 > 6 > 4라는 사이클이 존재한다. 이외의 경우는 자기 자신으로 돌아오는 사이클이 존재하지 않는데 여기서 자기 자신으로 돌아오는 사이클이 없는 경우가 바로 팀에 속하지 않는 경우다. 발그림으로라도 설명을 해보자면 완..

문제 접근 방식 여태까지 풀어본 BFS 문제 중 가장 어려웠던 문제인 거 같다... 일단 문제에서 중요한 포인트는 출발지에서 도착지까지 가는 동안 벽은 한 개까지만 부술 수 있다는 것이다. 길을 이동할 때마다 벽을 부순 적이 있는지 여부를 어딘가에 기록해야 됐고 이를 사용해 벽을 부순 적이 없다면 벽을 부수고 갈 수 있고 벽을 부순 적이 있다면 벽을 만났을 때는 더 이상 못 가게 해야 했다. 그래서 기존에 좌표를 기록하던 클래스에 추가로 벽을 부순 적이 있는지 여부를 저장하는 변수를 추가했다. 이 정도까지만 구현하고 코드를 돌려봤을 때 테스트 케이스는 성공했지만 실제 제출 한 결과는 실패로 떴다. 방문 여부 기록을 벽을 부수지 않은 상태와 부순 상태가 공유하기 때문에 발생한 문제였는데 문제점을 인지하고 ..

문제 접근 방식 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 위 문제에 조건이 좀 추가된 문제로 불이 붙은 칸뿐만 아니라 곧 불이 붙을 칸도 피해서 빌딩을 탈출해야 한다. if (isVisited[x][y] || building[x][y] == '#') continue; if (isFired[x][y] != 0 && isFired[x][y] - 1 < cur.time + 1) continue; 코드로 표현하면 위와 같은데 벽이거나 이미 방문한 곳은 패스하고 불이 났거나 불이 붙을 예정인 칸..

문제 접근 방식 기존 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..