0과 1의 쉼터

풀이 [백준 2206] 벽 부수고 이동하기 [Java] 풀이 (0, 0)에서 (N - 1, M - 1)까지 최대 벽을 1개 부수며 도착할 수 있는 최단거리를 구하면 되는 문제다. 하나의 2차원 배열에 최단거리를 기록하기에는 어느 순간 벽을 부술때와 부수지 않는 경우 kyr-db.tistory.com 위 문제의 확장 버전이다. 벽을 최대 K개 부수며 이동할 수 있다. 이전 로직에서 탐색 중 벽이 아닌 부분을 만났을 때 처리하는 부분을 0 또는 1이 아니라, 지금까지 부순 횟수(smash) + 1로 변경해 처리해주자. 그리고 마찬가지로, 벽을 0 ~ 10개 부순 경우에 대한 이동경로를 기록해야 하니 2개가 아닌, K+1개로 아래처럼 공간을 할당해 주자. 소스코드 소스코드 보기 출처 14442번: 벽 부수고 ..

풀이 출발지(from)와 목적지(to)에 대해 연결된 다리 중 최대중량을 구하는 문제다. 입력받은 다리의 중량제한에 대해 내림차순 정렬 후 순서대로 union시키며, from과 to가 동일한 집합에 속하는지(연결됬는지) 확인해주어 연결된 순간 union한 간선의 가중치가 최대 가중치이므로 출력하면 된다. 소스코드 소스코드 보기 출처 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net

풀이 (0, 0)에서 (N - 1, M - 1)까지 최대 벽을 1개 부수며 도착할 수 있는 최단거리를 구하면 되는 문제다. 하나의 2차원 배열에 최단거리를 기록하기에는 어느 순간 벽을 부술때와 부수지 않는 경우 중 어떤 경우가 더 빨리 도달할지 기록하기 어렵다. 때문에 두 경우에 대해 최단거리를 기록하고, 가장 먼저 (N - 1, M - 1)에 도달한 경우의 최단거리를 출력해주면 된다. 2차원 배열을 벽을 부수는 경우와 부수지 않는 경우로 하지 않고, queue에 넣어줄 때 현재의 최단거리를 가지고 있는 Point객체를 넣어주는 방식으로 풀이했다. bfs를 진행하며 다음 영역이 벽이 아니라면, 벽을 부순경우와 부수지 않은 경우 모두 아무 제한 없이 queue에 넣어주면 된다. 만약 다음 영역이 벽이라면,..

풀이 단순한 graph 문제이다. 입력을 받으면서 탐색 위치를(I)를 찾아주자. BFS로 풀이했다. 벽(X)이 아닌 경우와, 이미 방문하지 않은 공간을 탐색해주어야 한다. 위의 조건이 성립하고, 도연이가 사람(P)을 만났다면 만난 사람 수를 업데이트 해주자. 만약 만난 사람이 0명이라면 "TT"를 출력해주어야 한다는 점도 유의하자. 소스코드 소스코드 보기 출처 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net

풀이 각 지점에서 목표지점(2) 까지의 거리를 출력하는 문제로 반대로 생각해서 목표지점에서 출발해 갈 수 있는 모든 거리에 대한 거리를 계산하는 문제로 풀이할 수 있다. 입력을 받으면서 목표지점(=출발지점)을 찾으면 0으로 대신 넣어주고, 1이면 -1로 넣어주자. 그 외의 숫자는 그대로 넣어주면 된다. 1일 때 -1을 넣어주는 이유는 출발지점으로부터 출발했을 때 갈수없는 땅(0)으로 둘러싸인 영역은 도달할 수 없는 위치(-1)임을 미리 표시하기 위함이다. 출발지점에서 도달할 수 있는 영역의 1들이 전부 -1 로 바뀌면 문제가 없을까? 그렇다, 어차피 도달할 수 있는 영역의 거리들은 이전에 도달한 거리의 값(출발지점 = 0 이므로 0 이상의 수)에 1을 더한 값이기에 결국은 덮어쓰일 것이다. 그 이후로는 ..

풀이 뱀과 사다리 게임은 쉽게 출발지에서 주사위를 굴려 도착지까지 도달해야 하는 게임이다. 무조건 큰 숫자로 이동하는 '사다리'와 작은 숫자로 이동하는 '뱀' 이지만,'사다리-사다리' 보다 '뱀-사다리'가 더 빠를 수 있다는 점에 유의하자. 즉, 절대적으로 좋고(사다리) 안 좋은(뱀) 조건이 없다. 필자는 개인적으로 뱀을 좋아한다 (~쉬익~쉭) 그 때문에 이동 가능한 모든 칸에 대해서 탐색을 진행해야 한다. 다음 조건을 유의하자 주사위를 굴려 나온 수만큼 이동한 칸에 '사다리' 또는 '뱀'이 있을 때, 선택이 아닌 강제로 이동을 해야한다. '사다리'와 '뱀' 을 동시에 가지는 경우는 없다. 게임은 1회 이상 진행된다. 'N + M

풀이 두 수 A, B가 주어질 때 문제에서 정의된 D, S, L, R 명령을 사용해서 A를 B로 만드는 과정에서 사용한 명령을 순서대로 출력해주면 된다. 시간 제한은 6초로 넉넉한 편이기 때문에 Bidirectional Search 방식을 사용하지 않고, 기본 BFS 방식으로도 해결할 수 있다. 우선, 동일한 숫자가 만들어져 중복된 탐색을 방지하기 위해, 해당 숫자를 만들지 않은 경우에만 만들어줘야한다. queue에 해당 숫자를 만들기 위한 명령어를 set으로 묶어 넣어줘도 되지만, visited 배열에 넣어주기로 했다. 단 위의 방식을 사용할 경우 boolean값이 아닌, 문자열이 탐색 기준이 되기 때문에, 초기값과는 분명히 다른 시작값을 넣어주어야 한다. (초기값 : '-', 시작값 : '') que..

풀이 'Six Degrees of Separations' theory로도 불리는 이론이다. 자신과는 아무 연관성(inf or V) 없는 사람일지라도, 만약 친구가 한 명 이상 있다면(connected), 대부분 6단계(5명의 관계)를 걸쳐 알 수 있게 된다는 이론이다. 즉, 당신이 6단계를 넘어선다면 아싸일 확률이 매우 높... 문제에서 "모든 사람은 친구 관계로 연결되어져 있다." 라고 하여 주어지는 TC에 대한 별도의 예외처리는 없다. Floyd Warshall을 이용해 모든 친구 관계에 대해서 최단 단계를 구해주고, 각각의 유저가 모든 유저간에 대한 단계의 합으로이루어진 집합(step) 속 최솟값의 순번을 구하자. 소스코드 소스코드 보기 출처 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의..

풀이 수빈이가 동생한테 가는 방법은 현 위치(N)에 대해 3개의 방법(N + 1, N - 1, 2N)이 있다. 항상 N이 K에 가까워지는 방법이 정답이라는 보장이 없기 때문에 모든 경우에 대해 탐색을 해봐야 한다. Queue에 수빈이의 범위 내의 새로운 위치를 담아주고, 다시 꺼낼 때 이동 횟수를 기록한다. 단, 이미 방문한 위치를 재 방문할 때는 이동횟수가 같거나 크기 때문에 최소 이동횟수 기록을 보장하기 위해 방문하지 않은 경우에만 Queue에 담아두었다. Queue의 변화에 대해 궁금하다면 아래를 참고하자. 처음에 주어진 N(5)에 대한 3가지 이동 방법을 모두 기록하며, Queue에서 새로운 위치(nx)를 꺼낼때마다 이에 대한 이동 방법 또한 기록한다. 빨간색 대각선은 동일한 이동시간을 가진 위치..

풀이 배추흰지렁이는 인접한 배추(기준이 되는 배추로부터 상하좌우에 위치한 배추)로 퍼져나갈 수 있다. 따라서 인접한 배추들을 전부 탐색하고, visited에 탐색한 배추를 기록하고자 한다. 결국 인접한 배추들의 덩어리인 연결 요소(Connected Component)의 개수를 구하는 문제이다. 배추가 위치한 장소만을 탐색하기 위해 배추의 위치를 입력받을 때 배추의 위치를 location에 기록한 후, DFS의 시행횟수를 세어 풀이했다. 소스코드 소스코드 보기 출처 및 참고자료 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net