늦깎이 IT

[백준 14502번] 연구소 1. 벽을 3개 세우기 위해 DFS 완전탐색을 시작한다.2. 중복을 피하기 위해, 현재 시작점으로부터 오른쪽, 아래쪽 방향으로만 탐색을 진행한다.3. 벽을 3개 세웠으면, 그 상태에서 BFS 탐색으로 바이러스를 퍼뜨린다.4. 바이러스를 모두 퍼뜨렸으면, 안전지대를 세서 출력한다. [중복이 발생하는 코드] 12345678910111213141516171819202122232425public static void dfs(int numOfWall, int[][] prev) { int[][] temp = new int[N][M]; for (int i = 0; i

[백준 3190번] 뱀 1. 뱀의 몸통 좌표를 Deque 자료구조를 활용해서 저장한다. 머리를 움직일 때에는 Deque의 first에 추가하고 뱀의 꼬리를 자를 때는 Deque의 last에서 삭제한다. 2. 뱀의 전체 몸통이 차지하는 부분을 체크하기 위해 visited 배열을 선언하고, 뱀의 몸통이 위치한 자리마다true로 체크한다. 3. 현재 이동방향에 따라 머리를 한칸 전진시킨다.1) 머리를 전진시켰을 때, 이미 visited[row][col] = true이면, 뱀의 머리가 뱀의 몸통 중 일부를 만났다는 것이므로 종료한다.2) 머리를 전진시켰을 때, 사과가 있다면 뱀의 꼬리를 자르지 않는다.3) 머리를 전진시켰을 때, 빈칸이라면 꼬리를 자른다.4) 머리를 전진시켰을 때, 벽이라면 종료한다. 4. 현재..

[백준 13460번 구슬탈출2 URL]개인적으로, 시뮬레이션 문제 중에서 제일 어려웠던 문제.....방문 여부를 파악하기 위해 4차원 배열을 만들어야 했던 것도 생각하기 참 힘들었다. 시뮬레이션 과정은 다음과 같다.1. 구슬을 굴린다. - 구슬을 굴릴 때, 두 개의 구슬이 겹치든 말든 일단 굴린다. 2. 구슬을 굴리는 도중 - 만약, 구슬을 굴리는 도중 'O'을 만났다면, 멈춘다. 3. 구슬을 다 굴린 후 - 파란색 구슬이 'O'에 빠졌는지 "먼저" 확인한다. 파란색 구슬이 'O'에 빠졌다면 탐색을 종료한다. - 파란색 구슬은 'O'에 빠지지 않고, 빨간색 구슬이 'O' 빠졌다면 정답을 출력한다. - 어느 구슬도 'O'에 빠지지 않았다면, 두 구슬의 위치가 같은지 확인한다. - 두 구슬의 위치가 같다면,..

[백준 14888번 연산자 끼워넣기 URL] 모든 경우의 수를 모두 탐색하는 문제입니다.DFS 탐색을 사용하였습니다. [소스코드]123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collection;import java.util.Collections;import java..

[백준 14889번 스타트와 링크 URL] 1. N명을 반으로 나눠 한 팀은 스타트 팀, 나머지 한 팀은 링크 팀으로 나눈다.2. 팀을 나눌 때에는 DFS를 활용해서 모든 경우의 수를 구한다.2. 팀을 나눴다면, 조건에 의한 팀의 능력치를 계산한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103import java.io.BufferedReader;import java.io.IOException;..

[백준 15686번 치킨배달 URL] 사실 크게 어려운 문제는 아닙니다만, 여러 후보군 중에서 몇가지만을 선택하는 방법을 모르는 경우에는조금 난해할 수 있습니다. 이 문제에서 핵심인 K개의 치킨집이 있을 때 이중 M개만을 선택하고 다른 치킨집들을모두 폐업시켜야 하는 것입니다. M 개중에 K개를 선택하는 방법은 DFS를 활용하여 구현할 수 있습니다. [소스 코드]123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101..

[백준 14499번 주사위 굴리기 URL] 이번 문제는, 규칙성을 찾아내는 문제이다.문제에서 보는 것처럼, 초기 주사위의 위치와 그 값을 배열로 나타낼 경우 아래와 같이 나타낼 수 있다.이 상태에서 주사위를 동쪽으로 2번 굴렸을 때를 생각해보자. 아래 그림과 같이 나타낼 수 있다. 초기 단계에서 동쪽으로 굴리면 [뒷면, 앞면]을 제외한 나머지 면들이 변화하는 것을 볼 수 있다. 하지만 변화할 때 위에서 보는 것처럼 규칙성을 가지고 변화한다.1) 바닥면은 왼쪽면으로2) 왼쪽면은 윗면으로3) 오른쪽면은 바닥면으로4) 윗면은 오른쪽면으로바뀌는 것을 볼 수 있다. 이 규칙성은 주사위를 동쪽으로 굴렸을 경우에만 해당하는 것이기 때문에 서쪽, 남쪽, 북쪽도 마찬가지로규칙성을 찾아 문제를 풀면 된다. 12345678..

[백준 14500번 테트로미노 URL] 이 문제는 단순히 DFS 탐색으로 풀 수 있습니다.하지만, 아래 그림에 빨간 동그라미로 표시된 모양의 테트로미노는 DFS로 탐색할 수 없기 때문에 "ㅗ" 모양은따로 처리해야합니다. [코드]123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106import java.io.BufferedReader;import java.io.IOException;impo..