전체 글

1647 - 도시 분할 계획https://www.acmicpc.net/problem/1647문제마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이뤄짐길은 어느 방향으로든지 다닐 수 있고 길을 유지하는데 드는 유지비 있음마을을 2개의 분리된 마을로 분할할 계획 -> 분할 시 각 분리된 마을 안에 집들이 서로 연결 = 각 분리된 마을 안에 있는 임의의 두 집 사이 경로 항상 존재/ 마을에 집이 하나 이상 있어야 함, 분리된 마을 사이 있는 길 없앨 수 있음=> 길 모두 없애고 나머지 길의 유지비 합 최소입력첫째 줄: 집의 개수 N (2 다음 줄 ~ M줄: 길의 정보 A B C (1 (임의의 두 집 사이에 경로가 항상 존재하는 입력만 주어짐)출력: 없애고 남은 길 유지비의 합의 최솟값풀이Kruskal 알고..

2252 - 줄 세우기https://www.acmicpc.net/problem/2252문제N명의 학생 키 순서대로 줄 세움두 학생의 키를 비교하는 방법 사용 (모든 학생 다 비교 X 일부 O)=> 일부 학생들의 키 비교한 결과 주어졌을 때 줄 세우는 프로그램입력첫째 줄: N (1 다음 M개의 줄: 키를 비교한 두 학생의 번호 A, B (A가 B 앞에 서야 함)(학생들의 번호 1 ~ N번)출력: 학생들을 앞에서부터 줄을 세운 결과(답 여러 가지인 경우 아무거나 출력)풀이위상정렬(Topological Sort)방향이 있는 비순환 그래프(DAG; Directed Acyclic Graph)에서 모든 간선의 방향 지키며 정점 나열하는 것모든 정점의 진입차수(in-degree) 계산 -> 들어오는 간선 개수진입 차..

2533 - 사회망 서비스(SNS)https://www.acmicpc.net/problem/2533문제사회망에서 사람들의 친구 관계 그래프로 표현 (사이클 X) (사람 -> 정점 / 두 사람이 서로 친구 관계 -> 정점을 잇는 에지)-> 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정 이해얼리 어답터(early adaptor): 어떤 새로운 아이디어를 먼저 받아들인 사람/ 얼리 어답터가 아닌 사람은 자신의 모든 친구들이 얼리 어답터일 때만 이 아이디어 받아들임=> 친구 관계 트리가 주어졌을 때 모든 개인이 새로운 아이디어를 수용하기 위해 필요한 최소 얼리 어답터 수?입력첫째 줄: 친구 관계 트리의 정점 개수 N (2 두 번째 줄 N - 1개의 줄: 각 줄마다 친구 관계 트리의 에지(u, v) 나타..

16954 - 움직이는 미로 탈출https://www.acmicpc.net/problem/16954문제8x8 체스판에서 탈출하는 게임/ 모든 칸은 빈 칸 or 벽 중 하나시작: 가장 왼쪽 아랫 칸 / 도착: 가장 오른쪽 윗 칸1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고 가장 아래에 있어서 행 X -> 벽 사라짐1초에 인접한 한 칸 or 대각선 방향으로 인접한 한 칸 이동 or 현재 위치 서 있을 수 있음 (빈칸으로만 이동)1초 동안 캐릭터 먼저 이동 -> 벽 이동/ 벽이 캐릭터 있는 칸으로 이동하면 캐릭터 이동 X=> 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지입력: 8개 줄에 걸쳐 체스판 상태 주어짐 ('.' 빈칸 / '#' 벽)/ 가장 왼쪽 아랫칸 항상 벽 X출력: 가장 오른쪽 윗 칸..

4195 - 친구 네트워크https://www.acmicpc.net/problem/4195문제어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램(친구 네트워크: 친구 관계만으로 이동할 수 있는 사이)입력첫째 줄: 테스트 케이스 개수각 테스트 케이스 첫째 줄: 친구 관계 수 F (다음 F개의 줄: 친구 관계 생긴 순서(두 사용자 아이디 출력: 친구 관계 생길 때마다 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램풀이Union-Find`unf[fb] = fa`: `fb`를 `fa` 밑으로 붙임 = `fa`가 대표`size[fa] += size[fb]`: 두 네트워크 크키 합침`Map HM = new HashMap()`: 이름, 고유번호..

1717 - 집합의 표현https://www.acmicpc.net/problem/1717문제초기에 n + 1개의 집합 {0}, {1}, {2}, ..., {n}합집합 연산과 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산입력첫째 줄: n, m(: 입력으로 주어지는 연산의 개수)m개의 줄: 각각의 연산 (합집합: 0 a b = a가 포함되어 있는 집합과 b가 포함되어 있는 집합 합친다는 의미/ 1 a b: 두 원소가 같은 집합에 포함되어 있는지 확인)출력: 1로 시작하는 입력에 대해서 a와 b가 같은 집합 포함 O -> YES / X -> NO풀이Union-Find(Disjoint Set, 서로소 집합)여러 개의 원소가 있을 때 이 원소들이 어떤 그룹(집합)에 속하는지 관리하는 알고리즘시간 복잡도: ..