1939번: 중량제한
첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이
www.acmicpc.net
문제
N개의 섬으로 이루어진 섬들 사이에서 다리가 M개 설치되어 있다. 다리는 양방향으로 연결되어있고, c라는 최대 용량이 존재한다.
A섬에서 B섬으로 갈 때, 이동할 수 있는 다리 중 최대 용량을 옮길 수 있는 값을 출력해야 한다.
입력
N M
M개의 다리 (a, b, c) - 양방향
A섬 B섬
풀이
가장 먼저 생각한 방법은 다익스트라 였다. (무게를 내림차순으로 bfs를 도는 방식)
distance라는 int 배열을 통해 해당 섬으로 갔을 때의 최대 용량을 업데이트 하면서 bfs를 도는 방식이다. (최대 용량보다 낮다면 굳이 이후 작업을 할 필요가 없기 때문)
Add
문제를 풀고 다른 사람들의 코드를 보며 안 방법인데, 이분탐색 방식도 가능하다. 아래 코드추가 해놓음
코드 (메모리 초과)
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
static int N, M, start, end, answer;
static int[] distance;
static List<Node>[] lists;
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
distance = new int[N+1];
lists = new ArrayList[N+1];
answer = 0;
for(int i = 1; i <= N; i++) lists[i] = new ArrayList<Node>();
// A, B, C
// 1 <= A,B <= N
// 1 <= C <= 10억
for(int i = 0; i < M; i++) {
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
lists[a].add(new Node(b,c));
lists[b].add(new Node(a,c));
}
start = in.nextInt();
end = in.nextInt();
bfs();
System.out.println(distance[end]);
}
public static void bfs() {
PriorityQueue<Node> pq = new PriorityQueue<>();
distance[start] = 1000000001;
pq.add(new Node(start, 1000000001));
while(!pq.isEmpty()) {
Node node = pq.poll();
if(distance[node.next] > node.weight) continue;
for(int i = 0; i < lists[node.next].size(); i++) {
Node next = lists[node.next].get(i);
if(distance[next.next] > Math.min(node.weight, next.weight) ||
distance[end] > Math.min(node.weight, next.weight)) continue;
distance[next.next] = Math.min(node.weight, next.weight);
pq.add(new Node(next.next, Math.min(node.weight, next.weight)));
}
}
}
}
class Node implements Comparable<Node>{
int next;
int weight;
public Node(int next,int weight) {
this.next = next;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return o.weight - this.weight;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}class가 8바이트로 10만개를 추가해도 80만 바이트이기 때문에 128MB를 넘지 않으리라고 생각했다. 어디서 무한루프를 빠진다고 생각했고 문제가 되는 부분은 if(distance[next.next] > Math.min(node.weight, next.weight)) 였다. >=를 추가하지 않았다. 업데이트하면서 bfs를 돌지만 distance값과 Math.min 값이 같기 때문에 무한루프에 빠지는 것이였다.
코드 (정답)
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
static int N, M, start, end, answer;
static int[] distance;
static List<Node>[] lists;
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
distance = new int[N+1];
lists = new ArrayList[N+1];
answer = 0;
for(int i = 1; i <= N; i++) lists[i] = new ArrayList<Node>();
// A, B, C
// 1 <= A,B <= N
// 1 <= C <= 10억
for(int i = 0; i < M; i++) {
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
lists[a].add(new Node(b,c));
lists[b].add(new Node(a,c));
}
start = in.nextInt();
end = in.nextInt();
bfs();
System.out.println(distance[end]);
}
public static void bfs() {
PriorityQueue<Node> pq = new PriorityQueue<>();
distance[start] = 1000000001;
pq.add(new Node(start, 1000000001));
while(!pq.isEmpty()) {
Node node = pq.poll();
if(distance[node.next] > node.weight) continue;
for(int i = 0; i < lists[node.next].size(); i++) {
Node next = lists[node.next].get(i);
if(distance[next.next] >= Math.min(node.weight, next.weight) ||
distance[end] >= Math.min(node.weight, next.weight)) continue;
distance[next.next] = Math.min(node.weight, next.weight);
pq.add(new Node(next.next, Math.min(node.weight, next.weight)));
}
}
}
}
class Node implements Comparable<Node>{
int next;
int weight;
public Node(int next,int weight) {
this.next = next;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return o.weight - this.weight;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
이분탐색 코드 (정답)
ㄴimport java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
static int N, M, start, end, answer;
static List<Node>[] lists;
public static void main(String[] args) throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
lists = new ArrayList[N+1];
answer = 0;
for(int i = 1; i <= N; i++) lists[i] = new ArrayList<Node>();
int left = Integer.MAX_VALUE;
int right = Integer.MIN_VALUE;
for(int i = 0; i < M; i++) {
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
lists[a].add(new Node(b,c));
lists[b].add(new Node(a,c));
left = Math.min(left, c);
right = Math.max(right, c);
}
start = in.nextInt();
end = in.nextInt();
while(left <= right) {
int middle = (left + right) / 2;
if(bfs(middle)) {
left = middle + 1;
answer = middle;
}
else right = middle - 1;
}
System.out.println(answer);
}
public static boolean bfs(int weight) {
Queue<Node> q = new LinkedList<>();
boolean[] visited = new boolean[N+1];
q.offer(new Node(start, 0));
while(!q.isEmpty()) {
Node node = q.poll();
if(node.next == end) return true;
for(int i = 0; i < lists[node.next].size(); i++) {
Node next = lists[node.next].get(i);
if(weight <= next.weight && !visited[next.next]) {
visited[next.next] = true;
q.add(next);
}
}
}
return false;
}
}
class Node{
int next;
int weight;
public Node(int next,int weight) {
this.next = next;
this.weight = weight;
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [프로그래머스/Java] 시소 짝꿍 - Level 2 (0) | 2024.05.08 |
|---|---|
| [프로그래머스/Java] 호텔 대실 - Level 2 (0) | 2024.05.06 |
| [BOJ/JAVA] 백준 1753번 : 최단경로 (0) | 2024.01.22 |
| [BOJ/JAVA] 백준 5052번 : 전화번호 목록 (0) | 2024.01.18 |
| [BOJ/JAVA&GO] 백준 2467번 : 용액 (0) | 2024.01.15 |