java는 함수로 처리하면 더 빠르다? #3
Answered
by
yjsohn
wjdgns7712
asked this question in
Q&A
-
|
BOJ_3860_할로윈 묘지를 풀면서 궁금한점이 생겼는데, 이 부분에 대해서 다른분들 생각이 궁금해서 올려봅니다!
우선 오늘 하루종일 이 문제때문에 정말 힘들었습니다ㅠㅠ 아무튼, 제가 궁금한건 크게 2가지 입니다.
로직은 맞다고 생각하고 제출하는데 계속해서 틀리길래 너무 지쳐서 다른분들 풀이를 찾아봤습니다. 그런데 도착점에서 간선을 생략하더라구요... 그래서 저도 도착점 간선생성을 건너뛰었더니 바로 정답이 되긴했는데.. 왜 그런지 궁금합니다!
저는 굳이 여러번 반복호출도 안되는데 함수로 따로 만들 필요가 없다고 생각해서 메인아래에 쭉 썼더니 1600~1800ms가 나옵니다.. 함수로 구현한 경우가 왜 더 빠른걸까요?? 그리고 저렇게 약 2배정도 차이 날 정도인가요?? 다음은 참고한 코드입니다.
import java.io.*;
import java.util.*;
// 3860 할로윈 묘지
public class Main {
static class Edge {
Point start, end;
int cost;
public Edge(Point start, Point end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
}
static class Point {
int y, x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}
static int W, H, G, E; // W : 맵의 가로 H : 세로 G : 묘비의 개수 E : 귀신 구멍 수
static int[][] map; // -1 : 묘비 1 : 귀신구멍
static long[][] dist;
static ArrayList<Edge> edgeList;
static boolean infFlag;
// 좌표이동용 변수
static final int[] dr = { -1, 1, 0, 0 };
static final int[] dc = { 0, 0, -1, 1 };
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder(); // 정답 출력용
for (;;) {
// 1. 입력 & 초기화
StringTokenizer st;
st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
// 0-0 이 입력되면 종료
if (W == 0 && H == 0)
break;
map = new int[H][W];
dist = new long[H][W];
infFlag = false;
// 묘비 입력
G = Integer.parseInt(br.readLine());
int x, y;
for (int i = 1; i <= G; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
// 묘비는 못 가는 곳이므로 map에 -1 표시
map[y][x] = -1;
}
// 귀신구멍 입력
E = Integer.parseInt(br.readLine());
edgeList = new ArrayList<Edge>();
int x1, y1, x2, y2, t;
for (int i = 1; i <= E; i++) {
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken());
y1 = Integer.parseInt(st.nextToken());
x2 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
t = Integer.parseInt(st.nextToken());
// 귀신구멍에 1 표시
map[y1][x1] = 1;
// 간선리스트에 Edge 추가
edgeList.add(new Edge(new Point(y1, x1), new Point(y2, x2), t));
}
// 2. BFS로 가능한 모든 경로를 edgeList에 추가하기
makePath();
// 3. 밸만 포드
// ** dist는 출발지 1 제외하고 모두 무한대로
BellmanFord();
// 4. 출력
// 4-1. 무한루프가 가능하면 -1 출력
if (infFlag) {
sb.append("Never\n");
}
// 4-2. 무한루프 없으면 모든 도시의 최솟값 출력
else {
if (dist[H - 1][W - 1] == INF) {
sb.append("Impossible\n");
} else {
sb.append(dist[H - 1][W - 1] + "\n");
}
}
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
static void makePath() {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
// 묘비 or 귀신구멍이거나 도착지이면 continue
if (map[i][j] != 0 || (i == H - 1 && j == W - 1)) continue;
for (int k = 0; k<=3; k++) {
int nr = i + dr[k];
int nc = j + dc[k];
if ( nr >=0 && nr <H && nc >= 0 && nc < W && map[nr][nc] >=0 ) {
edgeList.add(new Edge(new Point(i,j), new Point(nr, nc), 1));
}
}
}
}
}
static void BellmanFord() {
// dist INF로 초기화
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
dist[i][j] = INF;
}
}
// 출발점은 0으로
dist[0][0] = 0;
// 1. N - 1번 동안 간선 M을 모두 확인하기
for (int i = 0; i < W * H; i++) {
int len = edgeList.size();
for (int j = 0; j < len; j++) {
Edge now = edgeList.get(j);
Point start = now.start;
Point end = now.end;
// 1-1. 귀신구멍 출발지가 현재 무한대이면 continue
if (dist[start.y][start.x] == INF)
continue;
// 1-2. 최솟값으로 값 갱신 가능하면 갱신
dist[end.y][end.x] = Math.min(dist[end.y][end.x], dist[start.y][start.x] + now.cost);
}
}
// 2. 마지막으로 간선 M을 모두 확인해서 갱신이 발생하면 무한루프
int len = edgeList.size();
for (int j = 0; j < len; j++) {
Edge now = edgeList.get(j);
Point start = now.start;
Point end = now.end;
// 2-1. 귀신구멍 출발지가 현재 무한대이면 continue
if (dist[start.y][start.x] == INF)
continue;
// 갱신이 발생한다면 무한루프에 빠질 수 있음
if (dist[start.y][start.x] + now.cost < dist[end.y][end.x]) {
infFlag = true;
return;
}
}
}
}
import java.io.*;
import java.util.*;
public class Main {
static final int MAX = Integer.MAX_VALUE;
static class Point{
int r, c;
public Point(int r, int c){
this.r = r;
this.c = c;
}
}
static class Edge{
Point from, to;
int cost;
public Edge(Point from, Point to, int cost){
this.from = new Point(from.r, from.c);
this.to = new Point(to.r, to.c);
this.cost = cost;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int W = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
int[] dr = {-1, 0, 1, 0};
int[] dc = {0, 1, 0, -1};
int[][] state, dist;
ArrayList<Edge> edges;
while (W!=0 && H!=0){
edges = new ArrayList<>();
state = new int[H][W];
dist = new int[H][W];
for (int i = 0; i < H; i++)
Arrays.fill(dist[i], MAX);
dist[0][0] = 0;
int G = Integer.parseInt(br.readLine());
for (int i = 0; i < G; i++) {
st = new StringTokenizer(br.readLine());
int c = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
state[r][c] = 1;
}
int E = Integer.parseInt(br.readLine());
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int c1 = Integer.parseInt(st.nextToken());
int r1 = Integer.parseInt(st.nextToken());
int c2 = Integer.parseInt(st.nextToken());
int r2 = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
state[r1][c1] = -1;
edges.add(new Edge(new Point(r1, c1), new Point(r2, c2), t));
}
for (int r = 0; r < H; r++)
for (int c = 0; c < W; c++)
if (state[r][c]==0 && (r!=H-1 || c!=W-1))
for (int k = 0; k < 4; k++) {
int nr = r + dr[k];
int nc = c + dc[k];
if ((0 <= nr && nr < H) && (0 <= nc && nc < W) && state[nr][nc] != 1)
edges.add(new Edge(new Point(r, c), new Point(nr, nc), 1));
}
for (int i = 0; i < W*H-G-1; i++)
for (Edge e : edges)
if (dist[e.from.r][e.from.c] != MAX)
dist[e.to.r][e.to.c] = Math.min(dist[e.to.r][e.to.c], dist[e.from.r][e.from.c]+e.cost);
never:{
for (Edge e : edges)
if (dist[e.from.r][e.from.c] != MAX && dist[e.to.r][e.to.c] > dist[e.from.r][e.from.c]+e.cost) {
bw.write("Never\n");
break never;
}
if(dist[H-1][W-1]==MAX)
bw.write("Impossible\n");
else
bw.write(dist[H-1][W-1]+"\n");
}
st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
}
bw.flush();
bw.close();
br.close();
}
} |
Beta Was this translation helpful? Give feedback.
Answered by
yjsohn
Aug 11, 2021
Replies: 3 comments 2 replies
-
|
주석을 달아놓는 습관이 들어있지않아 코드읽기 힘드신부분 죄송합니다ㅠ |
Beta Was this translation helpful? Give feedback.
0 replies
-
|
2번 질문에 대해서는 제가 자바를 사용하지 않아 답변 드릴 순 없지만.. 1번은 할로윈 묘지 지문 세 번째 문단에 있는 “ 그리고 상근이는 이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나갈 생각이다.” 이 문장 때문에 도착점에서 간선을 생성하면 안됩니다. 저도 이 문제 때문에 엄청 애먹었네요..ㅎㅎ |
Beta Was this translation helpful? Give feedback.
1 reply
-
|
아..!! 제가 문제해결만 생각해서 제대로 지문을 안읽어 그부분을 놓쳤네요.. 감사합니다!! |
Beta Was this translation helpful? Give feedback.
Answer selected by
wjdgns7712
-
|
2번 질문에서 제가 아는 선에서 예기 하자면 메소드를 사용하면 그에 대한 정보를 관리해야하기때문에 속도에 영향이 없다고 보기는 힘들어요 다만 캄퓨터속도가 빠르기때문에 저희처럼 테스트나 간단한 코드들은 영향이 거의 없다고 보시면 될듯해요. |
Beta Was this translation helpful? Give feedback.
1 reply
-
|
ㅠㅠ 어렵군요... 자바는.. |
Beta Was this translation helpful? Give feedback.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2번 질문에 대해서는 제가 자바를 사용하지 않아 답변 드릴 순 없지만.. 1번은 할로윈 묘지 지문 세 번째 문단에 있는 “ 그리고 상근이는 이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나갈 생각이다.” 이 문장 때문에 도착점에서 간선을 생성하면 안됩니다. 저도 이 문제 때문에 엄청 애먹었네요..ㅎㅎ