Algorithm/그래프(Graph)

[백준, Java] 2623번 : 음악프로그램

🔗 문제 링크 https://www.acmicpc.net/problem/2623 😮 문제 해결 방법 위상 정렬을 이용해 서로의 순서를 구해준다. 입력에 대해 그래프를 생성한다. 입력에 대해 순서에 따라 indegree 배열의 개수를 카운팅해준다. 위상 정렬을 이용해 순서를 리스트에 담아준다. 리스트 사이즈가 N보다 작은 경우 순서를 보장할 수 없는 경우 → 0을 반환 그 외 순서 리스트를 반환해 출력한다. 🚩 Java 코드 package com.second.algorithm.baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public ..

[프로그래머스, Java] 합승 택시 요금

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72413 😮 문제 해결 방법 최단 거리 알고리즘을 적용하는 것이 문제의 키포인트이다. 모든 도시로부터 출발해 모든 도시로 도착하는 최단 거리를 구해준다. 최단 거리를 구하는 방식은 크게 두가지가 있다. (무방향 양수 그래프 기준) 하나의 정점 기준 최단 거리구하기 → 다익스트라 알고리즘 : 모든 도시에 대해 구해야하므로 for문을 통해 모든 최단 거리를 구한다. 모든 정점 기준 최단 거리 구하기 → 플로이드 워셜 알고리즘 모든 정점에 대한 최단거리를 구하는 알고리즘은 플로이드 워셜을 일반적으로 사용하기 때문에 플로이드 워셜 알고리즘을 통해 문제를 해결한다. (다익스트라 이용시 시간초과 ..

[백준, Java] 1414번 : 불우이웃돕기

🔗 문제 링크 https://www.acmicpc.net/problem/1414 😮 문제 해결 방법 문제의 입력이 인접행렬 방식으로 들어오고, 알파벳과 0으로 들어온다. 따라서, 입력이 이어진 랜선의 길이이기 때문에 숫자로 변환하고 그래프를 만들어준다. 모든 컴퓨터에 대해 랜선 그래프를 만들어 줬으므로 모든 컴퓨터가 이어질 수 있게 가장 짧은 랜선을 구하면 된다. 따라서, 최소신장트리를 구하는 프림 혹은 크루스칼 알고리즘을 이용해 구현하면 문제를 해결할 수 있다. 알파벳을 숫자로 변환환다. 컴퓨터에 대해 랜선 정보를 연결한다(정점과 간선을 이용해 그래프 생성) 프림 알고리즘을 수행한다. 어떤 컴퓨터에서 시작하더라도 모두 이어져야하므로 상관이 없다. 최소 길이 랜선을 구하고 전체 랜선 길이에서 빼준다. 🚩..

[백준, Java] 18352번 : 특정 거리의 도시 찾기

🔗 문제 링크 https://www.acmicpc.net/problem/18352 😮 문제 해결 방법 문제의 조건에서 최대 300,000개의 도시가 입력으로 주어질 수 있다고 명시했기 때문에, 인접행렬 방식이 아닌 인접 리스트 방식으로 해결해야한다. 시작 도시부터 도달할 수 있는 모든 도시에 대해 최단거리를 구하는 알고리즘은 “다익스트라"를 사용할 수 있다. 물론, 해당 문제에서도 다익스트라 알고리즘을 사용할 수 있지만, 각 도시간 거리가 1로 고정이 되어있기 때문에 BFS를 이용해서도 문제를 해결할 수 있다. 출발 도시를 시작으로 BFS를 구현한다. 연결된 도시 중 방문하지 않고, 현재 도시에서 거리에 +1 한 값보다 연결된 도시 거리가 멀다면 최단 거리로 갱신한다. 시작 도시로 부터 도달할 수 있는 ..

[백준, Java] 1707번 : 이분 그래프

🔗 문제 링크 https://www.acmicpc.net/problem/1707 🤔 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 😮 문제 해결 방법 이분 그래프는 문제에 나와 있는 것 처럼 정점끼리 이어진 그래프를 하나의 집합으로 보고 서로 연결된 정점끼리는 다른 두 그룹으로 속하게 하는 그래프를 말한다. 따라서, 이분 그래프를 판별하는 방법은 다음과 같다. 색칠되지 않은 모든 정점에 대해 BFS를 진행한다. BFS의 시작 정점을 임의의 색상으로 색칠한다. ..