woody

핵심포인트 플레이어 이동 동시에 이동한다는 컨셉은 항상 자주나온다. 이전에는 임시 저장소를 만들어 움직인 뒤 다시 원본 배열로 복사하는 방식을 사용했다. 이 방식은 for문을 남발하고 쓸데없이 코드가 길어지기 때문에 다른 방식을 사용해보고자 했다. 사실 플레이어 이동이라는 동작은 매 턴마다 발생하기 때문에, 배열에 턴을 의미하는 차원을 하나 추가하면 해결되는 문제였다. ex) map[i][j][turn] = map[i][j][turn - 1] 본 문제의 경우 하나의 턴에서도 미로가 회전하기 전과 후, 두 가지의 경우로 또 플레이어 위치가 나뉘므로 회전 여부를 의미하는 차원까지 추가해 총 4차원 배열로 플레이어 배열을 정의했다. *실수했던 부분은 플레이어 이동 시 누적합(+=)으로 플레이어 수를 관리해야하..

핵심포인트 몬스터 복제 시도 복제된 몬스터는 5번째 단계에서 깨어나야하므로 저장공간을 따로 만들어서 관리해준다. 몬스터 이동 8방향을 모두 살펴보고 우선순위에 따라 이동할 수 있으면 이동한다. 이동할 수 없는 경우에도 까먹지 말고 monsterMap에 기존 위치에 추가해줘야한다. 팩맨 이동 제일 핵심이 되는 부분이다. 두 가지 어려움을 겪었다. 첫 번째 최초 우선순위에 따라 정방향으로 백트래킹을 활용해 가장 많이 몬스터를 잡아먹을 수 있는 경로를 탐색하는 방식으로 진행했다. 논리상으로는 문제가 없어보였지만, 만약 64개의 경로 중 어디에서도 몬스터를 잡아먹지 못해 이동경로 routes[]가 {0, 0, 0}으로 고정되어있다면 실제로 해당 방향으로 3칸 움직일 때 의도치 않은 ArrayIndexOutOfB..

핵심포인트 도망자 이동 동시에 움직이는 상황을 처리하기 위해서는 여러 가지의 방법을 사용할 수 있다. 이 문제를 해결할 때는 임시 저장공간을 만든 후, 원본 배열에서 임시 저장공간으로 움직인 후 다시 원본 배열로 복사하는 방식을 사용했다. 술래 이동 안에서 밖으로 이동 방향을 꺾을 때 까지 움직이는 칸 수를 나열해보면 1, 1, 2, 2, 3, 3, 4, 4, .... 이다. 따라서 방향을 꺾은 횟수와 현재 진행 방향에서 이동할 수 있는 남은 칸 수를 비교해가며 소용돌이 모양으로 움직여준다. 이 때 중요한 점은 *현재 바라보는 방향에서 끝까지 이동했다면 그 즉시 방향을 꺾는 것이다.* 마찬가지로 (0, 0) 에 도착했다면 방향을 즉시 꺾어줘야한다. 밖에서 안으로 이동 오히려 간단했다. 현재 밟은 칸에 대..

핵심포인트 시뮬레이션 진행 중 현재 가지고 있는 총과 바닥에 있는 총들 중 가장 공격력이 강한 총을 줍고 본인의 총은 내려놓는 상황이 많다. 해당 동작을 메소드로 만들어 필요할 때 마다 호출해 사용 바닥에 총이 하나가 아니라 여러개가 있을 수 있으므로, 매 번 다수의 총 중에 가장 공격력이 강한 것을 찾기위해 sort를 진행하면 시간적으로 손해가 생긴다. gunMap[][]은 우선순위 큐를 사용해 공격력이 큰 순으로 바로 뽑을 수 있게 준비하는 방식을 선택했다. 내부 클래스 Player는 Comparable을 상속받아 싸움이 붙었을 때의 승리 조건대로 정렬기준을 만들어줬다. 이렇게 하면 한 칸에 두 명의 플레이어가 있을 때, Collections.sort()를 통해 바로 승자와 패자를 구분할 수 있다. ..

문제소개 해결과정 다음과 같은 단계를 통해 풀이했다. 우선 출력 조건에 있듯이, 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력해야한다. -> 사전에 수록되어 있는 문자열의 개수를 먼저 구해야함 -> a의 개수 n, z의 개수 m이 있을 때 나올 수 있는 경우의 수는 n+m_C_n -> 경우의 수 K가 최대 십억까지 가능 -> 경우의 수가 너무 많다. dp를 통해 구해야함 dp[][] 배열을 구했으면 K번째에 있는 문자열을 구해야한다. -> 편하게 모든 것은 a를 기준으로 생각한다. -> K번째 자리에 최초 a가 올 지, z가 올 지는 어떻게 판단할까? -> a를 뽑은 경우의 수는 n+m-1_C_n-1 개가 된다. -> z를 뽑은 경우의 수는 바로 뒤부터 n+m-1_C_n 개가 존재한다...

문제소개 첫 번째 풀이 dfs로 탐색하는데, 무조건 위로 붙어서 가는게 좋다. (우상, 우, 우하 방향의 우선순위를 가짐) 실수한 점은, 단 하나의 경로만 선택되어야 하므로 3가지 경로에 대해 반복문으로 돌리다가 선택 가능한 상황이 있다면 *나머지 경우는 아예 탐색을 안하도록 만들었었다.* 하지만 이렇게 하면 문제가 발생한다. 어떤 임의의 지점 A에서 우상 방향으로 갈 수 있어 재귀 함수를 호출하고 나머지는 폐기한 상황에서, 이 경로가 끝까지 도달할 수 없는 경우일 수 있다. 그렇다면 A로 다시 돌아와 우상 방향은 갈 수 없으므로 다음 방향인 우 방향을 탐색하려 시도해야하는데, 폐기시켰으므로 그냥 갈 수 없다로 결론나게된다. 따라서 끝에서의 도달 여부에 따라 true를 반환할 지, false를 반환할 지..

문제소개 첫 번째 시도 처음에는 문제를 깊게 생각안하고 단순하게 생각해 풀이에 실패했다. 우선 최초 주어진, 거짓말임을 아는 친구들을 모두 HashSet에 넣어줬다. 그 뒤, 날짜 별 파티장에 오는 친구들을 쭉 받으면서 거짓말임을 아는 친구와 같이 온 친구들을 모두 HashSet에 같이 넣어줬다. (동시에 날짜 별 파티장에 오는 친구들의 리스트를 기록해뒀다.) 이렇게 모든 루프를 돌리면, 거짓말임을 아는 친구들이 모두 HashSet에 들어있다고 판단해 다시 처음부터 루프를 돌리며 한 명이라도 HashSet에 포함되어있다면 그 날은 거짓말을 못하는 날이라고 결론지었다. 하지만 이 풀이에는 오점이 있다. 상황을 예로 들어보자. 1번은 거짓말임을 아는 친구이다. 첫 날은 2, 3번 친구들이 파티장에 온다. 다..

문제소개 Solution1 첫 번째 풀이는 지나온 알파벳을 담는 HashSet과 배열의 방문여부를 나타내는 visited, 두 가지를 이용해 백트래킹으로 풀이했다. public class Main { static HashSet set; static char[][] map; static int R, C, max; static int[] dx = {1, -1, 0, 0}; static int[] dy = {0, 0, 1, -1}; static boolean[][] visited; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.i..

백준의 N과 M 시리즈는 순열, 조합을 익히기 좋은 예제이다. 1번부터 4번은 아래와 같이 내용을 다루고 있다. 순열 조합 중복순열 중복조합 모두 백트래킹을 활용해 풀이했다. 나중에도 쉽게 기억하기 위해 나름 정리해보자면 아래의 표와 같다. 순열 조합 반복문 시작 인덱스 처음부터 자신을 호출한 인덱스(start) 다음부터 visited 여부 visited가 필요함 오름차순으로 요소가 정렬되어있다면 visited 필요없음 매개변수 정보 count만 count와 탐색을 시작할 인덱스 start가 필요함 중복 순열 중복 조합 visited 여부 중복 선택 가능하므로 이제 필요없음 원래 필요없음 재귀호출 시 변함 없음 중복 선택 가능하므로 start + 1이 아니라 그대로 넘김 N과 M(1) 순열 문제이다. /..

문제소개 해결과정 주어진 조건에 따라 현재 들어온 비행기의 최대값부터 채워넣는 방식으로 생각할 수 있다. 그리디로 생각해보면 최댓값에 해당되는 게이트에 이미 비행기가 채워져 있다면, 하나 전 게이트에 넣는 방식으로 풀 수 있다. 하지만 이렇게 풀이하면 최악의 경우 10^5 * 10^5의 시간복잡도가 발생하므로 풀이할 수 없다. 문제의 포인트는 현재 N의 최댓값을 가지는 비행기가 들어왔을 때, 반복문을 통해 들어갈 게이트를 찾는게 아니라 바로 어디에 들어갈지 알 수 있어야 한다는 점이다! 이를 해결하기 위해 *유니온 파인드*를 활용했다. 최댓값 N을 가지는 비행기가 들어왔을 때, N-1번의 게이트와 union() 메소드를 통해 연결한다. 다음에 또 최댓값 N을 가지는 비행기가 들어왔을 때 find() 메소..