문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 풀이 골드 1이라는 난이도답게 BFS와 여러 가지를 섞었던 문제였다. 우선 문제의 핵심은 주어진 섬을 모두 연결할 수 있는 다리를 건설하는데 발생하는 최소비용을 구하는 것이다. 해당 문구를 통해서 섬이라는 정점을 모두 연결해야 하는 MST라고 유추할 수 있다. 원래 MST는 모든 정점을 연결하는 문제이지만, 해당 문제는 정점을 확대한 섬으로 계산을 해야 했기 때문에..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제가 굉장히 길었지만, 실제로는 문제의 유형을 알고 있다면 쉽게 풀 수 있는 문제였다. 내가 느끼기에 문제의 유형을 파악할 수 있는 부분은 다음과 같았다. 모든 섬을 최소한의 비용으로 연결해라! 다리를 여러번 건더더라도, 도달할 수 있으면 통행이 가능하다 다음 정보를 통해서 해당 문제는 MST(Minimum Spanning Tree)라고 생각했다. MST 문제도 주어진 N개의 ..
문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 문제 풀이 앞에서 풀었던 1197 최소 스패닝 트리에서 입력형식만 바뀐 거지 문제 풀이는 똑같다. 앞선 문제에서 주어졌던 입력 형식인 from->to->value가 배열 형식으로 i -> j -> input값으로 바뀐것이다. 따라서 해당 입력형식에 따라 노드를 생성하고, 크루스칼 알고리즘을 사용하면 쉽게 풀 수 있다. 전체 코드 package MST.`16398_행성_연결`.LJH impor..
문제 https://www.acmicpc.net/problem/27498 27498번: 연애 혁명 신촌고등학교 학생회장 기령이는 최근 학생들의 복잡한 사랑관계로 인해 고민이 많다. 학생들이 공부에 집중하지 못해 전반적인 성적이 하락하고 있는 것이다. 이에 기령이는 학생들의 복잡한 www.acmicpc.net 문제 풀이 저번 포스팅인 1197 최소 스패닝 트리를 풀면 아주 수월하게 풀 수 있습니다. 우선 문제가 굉장히 복잡해 보이지만, 핵심은 포기하도록 만드는 애정도의 합을 최소화하는것이 우리의 목표입니다. 우선 사랑관계는 여기서 정점들끼리의 간선으로 연결되어야한다는 뜻입니다. 문제에서 사랑관계가 이미 이루어진 관계는 반드시 포함되어야 한다고 정의했으므로, 사랑관계가 이루어진 관계는 반드시 간선에 포함시켜..
문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 풀이 MST를 구현하는 기본적인 문제이다. 우선 MST가 무엇인지에 대해서 알아야 한다. MST는 Minimum Spanning Tree이다. Spanning Tree의 조건은 V개의 정점이 있다면 V-1개의 간선을 이용해서 모든 정점을 연결할 수 있어야 한다. 그렇다면 MST는 모든 정점을 연결하면서 가중치의 합이 최소가 되어야 한다. 물..
