10282번: 해킹
최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면
www.acmicpc.net
- 풀이
다익스트라로 쉽게 풀 수 있을 거라고 생각했던 문제였지만 메모리 초과때문에 50분동안 고생했던 문제였습니다.
메모리 초과였던 코드와 통과 코드의 차이는 = 하나의 차이였습니다.
다익스트라에서 거리를 초기화시키면서 이동하는 distance라는 배열에서의 문제였습니다.
if(distance[next.b] < distance[now.b] + next.s) continue; //메모리 초과 코드if(distance[next.b] <= distance[now.b] + next.s) continue; // 통과 코드
해당 문제는 = 하나의 차이로 어떻게 메모리 초과가 발생한 이유는 간단했습니다.
d의 자료의 a,b,s 중 1,2,0이 있고 2,1,0이 있다고 가정합시다. 또한 다익스트라를 돌며 distance[1] = 10, distance[2] = 10으로 초기화 되어있습니다. 이 경우 1,2와 2,1를 계속 돌며 무한루프를 돌게되고 큐에 계속 추가되며 결국 메모리초과를 발생시키게 되었던 것이였습니다.
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
static StringBuilder sb;
static int n, d, c, count, sum;
static int[] distance;
static ArrayList<Node>[] array;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(sb);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
int testcase = in.nextInt();
sb = new StringBuilder();
distance = new int[10001];
for(int i = 0; i < testcase; i++) {
n = in.nextInt();
d = in.nextInt();
c = in.nextInt();
array = new ArrayList[n+1];
for(int j = 1; j <= n; j++)
array[j] = new ArrayList<Node>();
for(int j = 0; j < d; j++) {
int a = in.nextInt();
int b = in.nextInt();
array[b].add(new Node(a, in.nextInt()));
}
dijkstra();
count = 0;
sum = 0;
for(int j = 1; j <= n; j++) {
if(distance[j] == Integer.MAX_VALUE) continue;
count++;
sum = Math.max(sum, distance[j]);
}
sb.append(count + " " + sum).append("\n");
}
}
private static void dijkstra() {
PriorityQueue<Node> pq = new PriorityQueue<>();
Arrays.fill(distance, Integer.MAX_VALUE);
pq.add(new Node(c, 0));
distance[c] = 0;
while(!pq.isEmpty()) {
Node now = pq.poll();
for(Node next : array[now.b]) {
if(distance[next.b] <= distance[now.b] + next.s) continue;
distance[next.b] = distance[now.b] + next.s;
pq.add(new Node(next.b, distance[next.b]));
}
}
}
}
class Node implements Comparable<Node>{
int b;
int s;
public Node(int b, int s) {
this.b = b;
this.s = s;
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
return this.s - o.s;
}
}
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;
}
}
