전체 글 (168) 썸네일형 리스트형 백준 10159 저울 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 백준의 '여행 가자'라는 문제랑 흡사하다. 이 문제도 두 가지 버전으로 풀 수 있다. 첫 번째가 BFS, 두 번째가 플로이드 와샬 이다. 우선 BFS부터 살펴보자. 이 그래프는 단방향 그래프이고 양방향이 절대 될 수 없을 뿐더러 사이클도 생길 수 없기 때문에 트리구조다. 그래서 한 정점에서 BFS를 돌릴 때 접근되는 모든 점은 시작 정점보다 가볍다. 이 때 주의할 건 'A.. 백준 1976 여행가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행가고싶다... 이 문제는 두 가지 방법으로 풀 수 있다. 첫번째는 BFS, 두번쨰는 Union-Find이다 두 코드 다 수록했다. BFS로 푸는 건 각 정점간의 연결관계를 확인하는 방법이다. 예를 들어서 A - B, B - C가 연결되어 있을 때 A를 시작점으로 BFS를 돌리면 당연히 C까지 연결된다. A를 시작으로 하는 BFS를 돌리면서 도착하는 정점마다 A와 연결되어있다고 표시해두면 문제를.. 백준 15684 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 구현을 하면 되는데... 그 구현이... 너무 빡세다.... 가능한 모든 케이스를 대입하면 된다. 즉, 일일이 사다리를 넣어보고 주어진 조건을 만족하는 지 체크한다(이걸 무한반복...) /* 사다리 조작 */ #include #include #include using namespace std; void input(); void solve(); int N, M, H; bool ghost_leg[3.. 이전 1 ··· 36 37 38 39 40 41 42 ··· 56 다음