어흥

문제 링크: https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다. 그래프의 정점은 1부터 www.acmicpc.net 1. 주의할 점 - 단절점/단절선의 원리를 알고 있어야 한다 - 단절점과 다르게 Root Node의 Child수를 몰라도 되..

문제 링크: https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 1. 주의할 점 - 단절점에 대한 이론을 알고 있어야 한다 - 단절점이란 해당 점을 끊었을때 컴포넌트의 수가 증가하며, Root가 아닌 경우 단절점을 지나지 않고는 그보다 앞선 번호에 도달 할 수 없거나, Root인 경우 연결된 간선의 수가 2개 이상이면 무조건 단절점이다 2. 구현 - V[]벡터에 간선의 정보를 모두 저장한다 - DFS()를 통해 단절점을..

문제 링크: https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 �� www.acmicpc.net 1. 주의할 점 - 양의 사이클이 아닌, 가중치를 전부 -1로 곱하여 음의 사이클을 구하도록 한다 - 경로를 어떤 방식으로 저장할 것인가 - 사이클이 있다고 무조건 -1을 출력하는 것이 아니다 -> 도착지점까지 이동중, 음의 사이클이 존재한다면 -1 출력 2. 구현 - 음의 사이클이 존재하므로 벨만포드 알고리즘을 사용한다 - Bellman_ford() 함수..

문제 링크: https://www.acmicpc.net/problem/6987 6987번: 월드컵 www.acmicpc.net 1. 주의할 점 - 경우의수를 직접 구현해보려다가 실패했다. Set도 생각해 봤지만 그 팀의 가능한 승무패인지 확인만 해줄 뿐 그 이상의 가치는 없다. 즉, DFS로 풀자 2. 구현 - 토너먼트 형식으로 이루어져 있으므로, A팀과 B팀이 붙을 수 있는 경우의 수를 미리 구하여 T1[], T2[]에 넣는다 - 각 라인별을 6등분해서 3개씩 입력받아 한팀에 대한 정보를 Win[], Draw[], Lose[]에 담는다 - 만약 전체 팀의 경기수가 30이 안된다면 잘못된 경우로 간주한다(N*(N-1)번 만큼 경기가 이뤄져야 한다. 양쪽의 입장에서 간주하므로 2로 나누지 않는다) - DF..

문제 링크: https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다. 땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자. 이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미 www.acmicpc.net 1. 주의할 점 - DP를 통해 해결한다 - 왼쪽, 위, 왼쪽위 대각선을 살핀다(처음엔 오랜쪽으로 했는데 바꿨다) 2. ..

문제 링크: https://www.acmicpc.net/problem/3108 3108번: 로고 문제 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 �� www.acmicpc.net 1. 주의할 점 - 문제를 DFS+BFS를 이용하여 푸는 방법도 있지만, 제가 푼 방법은 범위를 비교하고 만약 서로 겹치는 점이 있다면 부모를 같게 하는 Disjoint-set 방법으로 해결했다 - 초기 상태 (0,0)에서 고개를 내리고 있으므로, (0,0)에 대한 정보를 포함시키고 시작해야한다. 1.5 범위 비교 - 범위 비교할때 다음과 같은 6가지의 경우만 겹치지 않는다고 판단했다 2. 구..

문제 링크: https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다 www.acmicpc.net 1. 주의할 점 - 무조건 H-G 도로를 지나가고 후보지까지 최단경로를 갱신했다면 정답에 포함한다 - 매 TC마다 초기..

문제 링크: https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 www.acmicpc.net 1. 주의할 점 - 음의 가중치인 간선이 존재하기 때문에, 벨만포드 알고리즘을 사용한다 - 시작 Node가 정해져 있지 않아서 D..