목록백준 (142)
mojo's Blog
[백준 16946] 벽 부수고 이동하기 4
문제 링크 => 16946번: 벽 부수고 이동하기 4 (acmicpc.net) 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 그래프 탐색을 이용한 문제이다. 먼저 이동할 수 있는 지점(0으로 구성된 곳)에 대해서 값을 먼저 세팅하도록 하였다. 문제에 있는 예시 2로 설명하자면 다음과 같다. 4 5 11001 00111 01010 10101 이때, 1은 이동할 수 없는 지점(벽)이므로 0으로 세팅하고 0으로 된 지점에서 그 다음 0으로 이동할 수 있는지를 파악하도록 한다. --- dp[N]..
[백준 4803] 트리
문제 링크 => https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 트리 문제이다. 이 문제의 핵심은 정점 2개가 주어질 때 방향이 존재하지 않는다는 것이다. 즉, a b 가 입력되면 a => b 가 될 수 있고, b => a 가 될 수 있다는 소리다. 따라서 이를 고려해서 코드를 작성해야 한다. (이부분을 몰라서 계속 틀렸다.) 임의의 정점들의 간선으로 이어진 그래프에 대해서 Cycle 이 존재하면 해당 그래프를 무시하도록 하고..
[백준 17412] 도시 왕복하기1
문제 링크 => 17412번: 도시 왕복하기 1 (acmicpc.net) 17412번: 도시 왕복하기 1 첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다. www.acmicpc.net 최대 유량을 이용하는 문제이다. 이 문제에서는 이전에 풀었던 최대 유량 문제와는 다르게 from에서 to로만 가는 단방향으로 연결되어 있다는 것이다. 따라서 2차원 배열 capacity를 채우는 과정은 c[from][to] = 1 만 해주면 끝이다. (from => to가 중복해서 나타나는 일이 없으므로 +는 하지 않음) 세팅이 끝나면 Edmond carp Algorithm 을 이용..
[백준 6086] 최대 유량
문제 링크 => 6086번: 최대 유량 (acmicpc.net) 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 최대 유량 문제이다. Edmond-carp Algorithm 을 이용하여 해결하였다. 문제에서 활용될 노드는 'A' ~ 'Z', 'a' ~ 'z' 이므로 총 52개의 노드가 필요하다. Input 을 보면 from, to, capacity 가 제공되는데 여기서 from, to 가 중복해서 나타나는 경우가 존재한다. 따라서 capacity를 노드에서 노드로 이동하는 2차원 배열 c[x][..
[백준 2254] 감옥 건설
문제 링크 => 2254번: 감옥 건설 (acmicpc.net) 2254번: 감옥 건설 첫째 줄에 N(1≤N≤1,000), Px, Py (-100,000≤Px, Py≤100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 볼록 껍질을 이용한 문제이다. 볼록 껍질을 형성하는 과정은 Graham Scan 방식을 이용하여 접근하였다. 다각형을 형성할 때 가장 바깥쪽에 위치하는 점들을 이용하여 다각형을 형성하고 소의 위치가 다각형 내부에 존재하는지 파악하면 된다. 소의 위치가 다각형 내부에 존재하는지 파악하는 여부는 CCW(cow, pi, p(i+1)) 의 값이 모두 동일한 경우 존재하고 그렇지..
[백준 16491] 대피소 찾기
문제 링크 => 16491번: 대피소 찾기 (acmicpc.net) 16491번: 대피소 찾기 지구에서 보낸 화성표면 탐사로봇은 2032년 현재 100개 이상이고, 그 개수가 빠르게 증가하고있다. 그 이유는 지구에는 없는 귀중한 금속 자원이 화성표면에서 속 속 발견되고 있기 때문이다. 화 www.acmicpc.net CCW 를 이용하는 문제이다. 대피소를 연결할 수 있는 모든 경우의 수 N! 를 permutation 을 통해서 구할 수 있고, 로봇과 대피소를 연결한 벡터 N개에 대하여 ((N-1)N / 2) 개 일때 모두 선분 교차가 일어나지 않는 경우 해당 대피소의 번호를 출력하면 된다. 일직선 위에 점이 존재하지 않는다는 조건이 없으므로 [백준 17386] 선분 교차 1 :: M - J - C (ti..