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에 넣어주면 된다. 만약 다음 영역이 벽이라면,..

풀이 이전에 풀었던 문제의 확장판이다. [백준 17352] 여러분의 다리가 되어 드리겠습니다! [Java] 풀이 N + 1개의 집합 1 ~ N에 대해 공통 부모가 다른 경우를 찾아 연결해주면 되는 문제다. 우선, 입력으로 두 집합을 입력받아 union해주자. 모든 입력을 받았다면, parents에 자신의 부모 집합의 번호 kyr-db.tistory.com 입력에 따라 union을 해주고, 최대 1000개 까지 주어지는 최대 200이하의 도시에 대해 여행계획이 가능한지, 즉 공통 부모가 다르지 않은지 확인하는 문제다. 입력받은 i번째 줄의 j번이 1이라면 i 에서 j는 연결된 도시이다. 마지막에 입력되는 여행 계획은 결국 도시들이 하나로 연결이 되어있는지 여부에 따라 여행 가능 여부가 결정된다. 즉, 공통..

풀이 N + 1개의 집합 1 ~ N에 대해 공통 부모가 다른 경우를 찾아 연결해주면 되는 문제다. 우선, 입력으로 두 집합을 입력받아 union해주자. 모든 입력을 받았다면, parents에 자신의 부모 집합의 번호가 적혀있을 것이다. 반복문을 돌며, 부모 집합의 번호가 다르다면 두 집합은 연결되어 있지 않으므로 두 집합을 연결할 수 있도록 번호를 출력해주면 되는 문제다. 소스코드 소스코드 보기 출처

풀이 트리로 주어지는 목차의 정보를 글머리 번호 형태로 바꾸면 되는 문제다. 아래 조건에 따라 변환할 수 있다. i 번째 수가 i - 1번째 수보다 작다면, 상위 글머리 번호부터 변환해주어야 한다. i 번째 수가 i - 1번째 수보다 크다면, 글머리 번호 형태에 따라 1로 변해야 한다. i 번째 수가 i - 1번째 수와 동일하다면, 이미 존재하는 목차이므로 i - 1번째 수의 글머리 번호 형태 + 1로 변해야 한다. 먼저 i번째 수가 i - 1번째 수보다 작은 경우다. 상위 글머리 번호부터 변환해주어야 하기에 이전에 기록된 하위 글머리 번호에 대해 누적된 수들을 0으로 초기화 하는 과정이 시간초과의 원인이 되었다. 이번 기회에 알게 된 사실인데, 문제를 틀렸거나 부분점수를 얻은 경우 '내 제출' 란에서 ..

풀이 N명의 학생들에 대해 각각 자신의 키가 몇 번째 순서인지 알아내는 문제다. 즉, N명의 키 순서에 대한 단방향 그래프에서 탐색하고자 하는 정점에서 출발하거나 도착하는 관계(간선) 에 대해 자신을 제외한 N - 1 명이 포함 되었는지 살피는 문제다. 가중치는 중요하지 않으니 1로 처리해 단순히 연결 여부만 기록하자. Floyd Warshall으로 탐색을 진행하며, 단방향 그래프에서 간접적으로 연결된 간선이 존재한다면 두 가중치의 합은 inf가 아니여야 한다. 동일하게 연결 여부만 1로 기록하자. 위의 과정을 진행했다면, 이제는 단방향 그래프속 자신이 갈수 있거나, 자신에게 올 수 있는 정점들의 갯수를 카운트 해야한다. 자기 자신이 아니면서( u != v ), 자신으로부터 갈수있는 정점이 아니고( gr..

풀이 단순한 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을 더한 값이기에 결국은 덮어쓰일 것이다. 그 이후로는 ..

풀이 주어진 트리에 대해 트리의 지름을 구하면 되는 문제다. [백준 1967] 트리의 지름 [Python] 에서 더 많은 정점을 입력받는 동일한 문제이지만, 이전 글의 풀이와 동일한 방법으로 문제를 해결할 수 있다. 다른 점이라 하면, 입력이 양방향 그래프로 주어지기 때문에 따로 처리하지 않아도 된다. 소스코드 소스코드 보기 출처 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net