uk's study

# 분류 : 이진 탐색, 투 포인터 알고리즘

# 백준 1208번 https://ukyonge.tistory.com/38 문제와 비슷하다. 하지만 반복문을 돌려 리스트에 저장해서 풀었을 때는 시간초과가 나서, 입력 받고 나서 계산하여 4개의 배열을 2개의 배열로 나누어 값을 넣어서 계산했더니 통과.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Arrays;

import java.util.StringTokenizer;

public class p7453 {

static int arr[][];

static long AB[], CD[];

static int N;

static long count=0;

public static void main(String[] args) throws NumberFormatException, IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

N = Integer.parseInt(br.readLine());

arr = new int[N][4];

AB = new long[N*N];

CD = new long[N*N];

StringTokenizer st;

int index=0;

for(int i=0; i<N; i++) {

st = new StringTokenizer(br.readLine());

arr[i][0] = Integer.parseInt(st.nextToken());

arr[i][1] = Integer.parseInt(st.nextToken());

arr[i][2] = Integer.parseInt(st.nextToken());

arr[i][3] = Integer.parseInt(st.nextToken());

}

for(int i=0; i<N; i++) {

for(int j=0; j<N; j++) {

AB[index] = arr[i][0] + arr[j][1];

CD[index] = arr[i][2] + arr[j][3];

index++;

}

Arrays.sort(AB);

Arrays.sort(CD);

int leftIndex = 0;

int rightIndex = N*N-1;

while(leftIndex<N*N && rightIndex>=0) {

long left_val = AB[leftIndex];

long right_val = CD[rightIndex];

if(left_val + right_val == 0) {

long left_count = 0;

while(leftIndex<AB.length && AB[leftIndex]==left_val) {

left_count++;

leftIndex++;

}

long right_count = 0;

while(rightIndex >= 0 && CD[rightIndex] == right_val) {

right_count++;

rightIndex--;

}

count += right_count * left_count;

}

if(left_val + right_val < 0) {

leftIndex++;

}

if(left_val + right_val > 0) {

rightIndex--;

}

System.out.println(count);

}

Colored by Color Scripter

cs

'백준' 카테고리의 다른 글

#백준_2632 피자판매 - Java (0)	2020.01.22
#백준_1525 퍼즐 - Java (0)	2020.01.21
#백준_1208 부분수열의 합 2 - Java (0)	2020.01.20
#백준_1261 알고스팟 - Java (0)	2020.01.19
#백준_2261 가장 가까운 두 점 (0)	2020.01.13

# 유형 : 투 포인터, 탐색

# 부분수열의 합 1(https://www.acmicpc.net/problem/1182) 에서는 2^20이어서 2초를 안넘겼지만, 이번 문제는 2^40이고 제한시간은 1초였다. 문제도 제대로 안읽고 1182번에서 푼 대로 접근해보았지만 당연히 시간초과.

어떻게 해결할지 생각해보다가 찾은 방법은 배열을 분할하여 푸는 방법이었다. 2^20은 약 1초만에 계산이 가능하기 때문에 가능한 방법.

[1,3,5,7,2,4,5,10] 을 [1,3,5,7] [2,4,5,10]으로 나누어 왼쪽의 부분집합의 합, 오른쪽의 부분집합의 합을 구하는 리스트를 구한 후, 정렬하여 투포인터 알고리즘을 사용하여 해결한다. 이 때 값들을 long 타입으로 안해줘서 74%정도에서 계속 틀렸습니다가 떠서 한참을 헤맸다.

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

package bj;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.Collections;

import java.util.StringTokenizer;

public class p1208 {

static int N,S;

static int arr[];

static ArrayList<Integer> left = new ArrayList<>();

static ArrayList<Integer> right = new ArrayList<>();

static long cnt=0;

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());

S = Integer.parseInt(st.nextToken());

arr = new int[N];

st = new StringTokenizer(br.readLine());

for(int i=0; i<N; i++)

arr[i] = Integer.parseInt(st.nextToken());

makeBinary(0, 0, N/2, left);

makeBinary(0, N/2, N, right);

Collections.sort(left);

Collections.sort(right);

int leftIndex = 0;

int rightIndex = right.size()-1;

while(leftIndex<left.size() && rightIndex>=0) {

long left_val = left.get(leftIndex);

long right_val = right.get(rightIndex);

if(left_val + right_val == S) {

long left_count = 0;

while(leftIndex<left.size() && left.get(leftIndex)==left_val) {

left_count++;

leftIndex++;

}

long right_count = 0;

while(rightIndex >= 0 && right.get(rightIndex) == right_val) {

right_count++;

rightIndex--;

}

cnt += right_count * left_count;

}

if(left_val + right_val < S) {

leftIndex++;

}

if(left_val + right_val > S) {

rightIndex--;

}

if(S==0)

System.out.println(cnt-1);

else

System.out.println(cnt);

}

public static void makeBinary(int sum, int start, int end, ArrayList<Integer> list) {

if(start >= end) {

list.add(sum);

return;

}

makeBinary(sum, start+1, end, list);

makeBinary(sum+arr[start], start+1, end, list);

}

Colored by Color Scripter

cs

'백준' 카테고리의 다른 글

#백준_1525 퍼즐 - Java (0)	2020.01.21
#백준_7453 합이 0인 네 정수 - Java (0)	2020.01.20
#백준_1261 알고스팟 - Java (0)	2020.01.19
#백준_2261 가장 가까운 두 점 (0)	2020.01.13
#백준_1517 버블 소트 (0)	2020.01.13

유형 : 탐색, 다익스트라, 우선순위큐, BFS

# 푸는 방법 : 0인 곳으로 이동할 때는 dist를 증가시켜주지 않고, 1인곳으로 이동할 때는 dist를 증가시켜 주는데

두 정점을 구분하기 위해 탐색할때 다익스트라를 이용한 우선순위큐 또는 Deque를 사용한다.

1) Priority queue를 이용한 다익스트라

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.PriorityQueue;

import java.util.Queue;

import java.util.StringTokenizer;

public class Main {

static int M,N;

static int count=0;

static int arr[][];

static int dist[][];

static boolean visit[][];

static int moveX[] = {0,1,0,-1};

static int moveY[] = {-1,0,1,0};

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

M = Integer.parseInt(st.nextToken());

N = Integer.parseInt(st.nextToken());

arr = new int[N][M];

visit = new boolean[N][M];

dist = new int[N][M];

for(int i=0; i<N; i++)

for(int j=0; j<M; j++)

dist[i][j] = Integer.MAX_VALUE;

for(int i=0; i<N; i++) {

String str = br.readLine();

for(int j=0; j<M; j++) {

arr[i][j] = str.charAt(j)-'0';

}

bfs(new P(0,0,0));

System.out.println(count);

}

public static void bfs(P p) {

PriorityQueue<P> pq = new PriorityQueue<>();

pq.add(p);

int y = p.y;

int x = p.x;

dist[y][x] = 0;

while(!pq.isEmpty()) {

P tmp = pq.poll();

x = tmp.x;

y = tmp.y;

int cnt = tmp.cnt;

// System.out.println(y+" "+x+" "+cnt);

if(x==M-1 && y==N-1) {

count = cnt;

return;

}

for(int d=0; d<4; d++) {

int newX = x + moveX[d];

int newY = y + moveY[d];

if(0<=newX && newX<M && 0<=newY && newY<N) {

if(dist[newY][newX] > dist[y][x] + arr[newY][newX]) {

dist[newY][newX] = dist[y][x] + arr[newY][newX];

pq.add(new P(newX,newY,dist[y][x] + arr[newY][newX]));

}

public static class P implements Comparable<P>{

int x;

int y;

int cnt;

public P(int x,int y,int cnt) {

this.x=x;

this.y=y;

this.cnt=cnt;

}

@Override

public int compareTo(P o) {

// TODO Auto-generated method stub

return this.cnt - o.cnt;

}

Colored by Color Scripter

cs

2) Deque를 이용한 방법

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

package bj;

import java.awt.Point;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Deque;

import java.util.LinkedList;

import java.util.PriorityQueue;

import java.util.Queue;

import java.util.StringTokenizer;

public class p1261 {

static int M,N;

static int count=0;

static int arr[][];

static int dist[][];

static boolean visit[][];

static int moveX[] = {0,1,0,-1};

static int moveY[] = {-1,0,1,0};

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

M = Integer.parseInt(st.nextToken());

N = Integer.parseInt(st.nextToken());

arr = new int[N][M];

visit = new boolean[N][M];

dist = new int[N][M];

// for(int i=0; i<N; i++)

// for(int j=0; j<M; j++)

// dist[i][j] = Integer.MAX_VALUE;

//

for(int i=0; i<N; i++) {

String str = br.readLine();

for(int j=0; j<M; j++) {

arr[i][j] = str.charAt(j)-'0';

}

// bfs(new P(0,0,0));

bfs_usingDeque(new Point(0,0));

System.out.println(dist[N-1][M-1]);

// System.out.println(count);

}

public static void bfs_usingDeque(Point p) {

Deque<Point> deque = new LinkedList<>();

int x = p.x;

int y = p.y;

deque.addLast(p);

while(!deque.isEmpty()) {

Point tmp = deque.pollLast();

x = tmp.x;

y = tmp.y;

for(int d=0; d<4; d++) {

int newX = x + moveX[d];

int newY = y + moveY[d];

if(0<=newX && newX<M && 0<=newY && newY<N && !visit[newY][newX]) {

if(arr[newY][newX] == 0) {

dist[newY][newX] = dist[y][x];

deque.addLast(new Point(newX,newY));

}else {

dist[newY][newX] = dist[y][x] + 1;

deque.addFirst(new Point(newX,newY));

}

visit[newY][newX] = true;

}

public static void bfs(P p) {

PriorityQueue<P> pq = new PriorityQueue<>();

pq.add(p);

int y = p.y;

int x = p.x;

dist[y][x] = 0;

while(!pq.isEmpty()) {

P tmp = pq.poll();

x = tmp.x;

y = tmp.y;

int cnt = tmp.cnt;

// System.out.println(y+" "+x+" "+cnt);

if(x==M-1 && y==N-1) {

count = cnt;

return;

}

for(int d=0; d<4; d++) {

int newX = x + moveX[d];

int newY = y + moveY[d];

if(0<=newX && newX<M && 0<=newY && newY<N) {

if(dist[newY][newX] > dist[y][x] + arr[newY][newX]) {

dist[newY][newX] = dist[y][x] + arr[newY][newX];

pq.add(new P(newX,newY,dist[y][x] + arr[newY][newX]));

}

public static class P implements Comparable<P>{

int x;

int y;

int cnt;

public P(int x,int y,int cnt) {

this.x=x;

this.y=y;

this.cnt=cnt;

}

@Override

public int compareTo(P o) {

// TODO Auto-generated method stub

return this.cnt - o.cnt;

}

Colored by Color Scripter

cs

'백준' 카테고리의 다른 글

#백준_7453 합이 0인 네 정수 - Java (0)	2020.01.20
#백준_1208 부분수열의 합 2 - Java (0)	2020.01.20
#백준_2261 가장 가까운 두 점 (0)	2020.01.13
#백준_1517 버블 소트 (0)	2020.01.13
#백준_11404 플로이드 - Java (0)	2020.01.11

#유형 : 분할 정복

# 간단한 알고리즘으로는 시간 초과를 벗어날 수 없음.. 풀었던 방법은

1) X좌표를 기준으로 정렬을 하여 middle index를 기준으로 왼쪽,오른쪽에서 가장 가까운 거리, middle 을 가로지르는 두 점간의 가장 가까운거리 3가지를 구해야 한다.

2) 왼쪽에서 가장 가까운 두점 사이의 거리, 오른쪽에서 가장 가까운 두점사이의 거리를 구하여 Min_value를 정해놓고, 이 값을 이용하여 middle index를 가로지르는 두 점간의 가장 가까운 거리를 구하여 min_value보다 작은 값들을 리스트에 넣는다.

3) 리스트를 Y좌표를 기준으로 정렬을 하여 y좌표들 간의 거리의 제곱이 stand보다 작은 값들만 거리를 구해서 비교하며 최솟값을 찾으면 된다.


package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class p2261 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList arrList = new ArrayList<>();
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y= Integer.parseInt(st.nextToken());
			arrList.add(new Point(x,y));
		}
		
		Collections.sort(arrList);
		System.out.println(solve(arrList, 0, N-1));
	}
	
	
	static int solve(ArrayList p, int x, int y) {
		int limit = y-x+1;
		
		if(limit<=3)
			return search(p, x, y);
		
		int middle = (x+y)/2;
		int left = solve(p, x, middle);
		int right = solve(p, middle+1, y);
		int stand = Math.min(left, right);
		
		ArrayList tmp = new ArrayList<>();
		for(int i=x; i<=y; i++) {
			int dist = p.get(i).x - p.get(middle).x;
			if(dist*dist < stand)
				tmp.add(p.get(i));
			
		}
		
		Collections.sort(tmp, new point_compartor());
		
		int size = tmp.size();
		for(int i=0; i<size-1; i++) {
			for(int j=i+1; j<size; j++) {
				int val = tmp.get(i).y - tmp.get(j).y;
				if(val*val < stand) {
					int d = getDistance(tmp.get(i), tmp.get(j));
					if(d < stand)
						stand = d;
				}else
					break;
			}
		}
		
		return stand;
	}
	public static int getDistance(Point p1, Point p2) {
		int result = (int) (Math.pow(p1.x-p2.x, 2) + Math.pow(p1.y - p2.y, 2));
		return result;
	}
	public static int search(ArrayList p, int x, int y) {
		int rs = -1;
		for(int i=x; i<=y-1; i++) {
			for(int j=i+1; j<=y; j++) {
				int val = getDistance(p.get(i), p.get(j));
				if(rs==-1 || rs>val)
					rs=val;
			}
		}
		return rs;
	}
	public static class Point implements Comparable{
		int x;
		int y;
		public Point(int x,int y) {
			this.x=x;
			this.y=y;
		}
		@Override
		public int compareTo(Point o) {
			int val = this.x - o.x;
			if(val == 0) {
				return this.y-o.y;
			}else
				return val;
		}
	}
	
	public static class point_compartor implements Comparator{

		@Override
		public int compare(Point o1, Point o2) {
			// TODO Auto-generated method stub
			return o1.y-o2.y;
		}
	}
}

'백준' 카테고리의 다른 글

#백준_1208 부분수열의 합 2 - Java (0)	2020.01.20
#백준_1261 알고스팟 - Java (0)	2020.01.19
#백준_1517 버블 소트 (0)	2020.01.13
#백준_11404 플로이드 - Java (0)	2020.01.11
백준_11657 타임머신 - Java 자바 (출력초과 수정완료) (0)	2020.01.11

# 유형 : 분할 정복, 정렬

# 제목은 버블 소트이지만, 버블 소트를 쓰면 바로 시간초과 남, 병합 정렬을 할 때 cnt를 세는 부분만 추가하면 된다. 카운트 증가는 병합 과정에서 왼쪽 값이 오른쪽 값 보다 클 때 왼쪽 배열에 있는 원소의 갯수만큼 계속 더해주면 된다.


package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p1517 {
	static long cnt=0;
	static long tmp[];
	static long arr[];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new long[N];
		tmp = new long[N];
		for(int i=0; i<N; i++)
			arr[i] = Long.parseLong(st.nextToken());
		
		mergeSort(0, arr.length-1);
		System.out.println(cnt);
	}
	
	public static void mergeSort(int begin, int end) {
		if(begin<end) {
			int middle = (begin+end)/2;
			mergeSort(begin, middle);
			mergeSort(middle+1, end);
			merge(begin,middle,end);
		}
	}

	private static void merge(int begin, int middle, int end) {
		// TODO Auto-generated method stub
		int i = begin;
		int j = middle+1;
		int t = begin;
		
		while(i<=middle && j<=end) {
			if(arr[i] <= arr[j]) {
				tmp[t++] = arr[i++];
			}else {
				tmp[t++] = arr[j++];
				cnt +=  (middle + 1 - i);
			}
		}
		while(i<=middle)
			tmp[t++] = arr[i++];
		while(j<=end)
			tmp[t++] = arr[j++];
		
		for(int k=begin; k<=end; k++) {
			arr[k] = tmp[k];
		}
		
	}
}

'백준' 카테고리의 다른 글

#백준_1261 알고스팟 - Java (0)	2020.01.19
#백준_2261 가장 가까운 두 점 (0)	2020.01.13
#백준_11404 플로이드 - Java (0)	2020.01.11
백준_11657 타임머신 - Java 자바 (출력초과 수정완료) (0)	2020.01.11
#백준_1654 랜선 자르기 - Java (0)	2020.01.11

자바 프로그래밍을 하다보면 객체를 정렬해야 할 경우가 자주 있다.

ex) 학생들을 국어 점수를 감소하는 순, 좌표를 x좌표가 증가하는 순 등..

객체의 정렬 기준을 명시하는 방법에는 두 가지가 있다.

1. Interface Comparable

2. Interface Comparator

1. Comparable

정렬 수행 시 기본적으로 적용되는 정렬 기준이 되는 메서드를 정의하는 인터페이스

> 구현 방법

정렬할 객체에 Comparable interface를 implements 후, compareTo() 메서드를 오버라이드하여 구현한다.

compareTo() 메서드 작성법 - 리턴 값이 0이나 음수면 기준값은 고정, 양수 값이면 바뀐다.

현재 객체 < 파라미터로 넘어온 객체: 음수 리턴
현재 객체 == 파라미터로 넘어온 객체: 0 리턴
현재 객체 > 파라미터로 넘어온 객체: 양수 리턴

Comparable Example


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class compa {
	public static void main(String[] args) {
		int x = 3, y = 4;
		List arrList = new ArrayList<>();
		arrList.add(new Point(x, y));
		x=1; y=1;
		arrList.add(new Point(x, y));
		Collections.sort(arrList);
		x=4; y= 7;
		arrList.add(new Point(x, y));
		for(int i=0; i<arrList.size(); i++) {
			System.out.println(arrList.get(i).x +" "+arrList.get(i).y);
		}
	}
	// x좌표가 증가하는 순, x좌표가 같으면 y좌표가 감소하는 순으로 정렬하라.
	static class Point implements Comparable {
	    int x, y;
	    
	    public Point(int x,int y) {
	    		this.x=x;
	    		this.y=y;
	    }
	    @Override
	    public int compareTo(Point p) {
	        if(this.x > p.x) {
	            return 1; // x에 대해서는 오름차순
	        }
	        else if(this.x == p.x) { // 같을경우에
	            if(this.y < p.y) { // y에 대해서는 내림차순
	                return 1;
	            }
	        }
	        return -1;
	    }
	}

}

2. Comparator

정렬 가능한 클래스(Comparable 인터페이스를 구현한 클래스)들의 기본 정렬 기준과 다르게 정렬 하고 싶을 때 사용하는 인터페이스

compare() 메서드 작성법 - 리턴 값이 0이나 음수면 기준값은 고정, 양수 값이면 바뀐다.

현재 객체 < 파라미터로 넘어온 객체: 음수 리턴
현재 객체 == 파라미터로 넘어온 객체: 0 리턴
현재 객체 > 파라미터로 넘어온 객체: 양수 리턴

Comparator Example


 	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList arrList = new ArrayList<>();
		StringTokenizer st;
		for(int i=0; i tmp = new ArrayList<>();
        ....
        Collections.sort(tmp, new point_compartor());
	}
	public static class Point implements Comparable{
		int x;
		int y;
		public Point(int x,int y) {
			this.x=x;
			this.y=y;
		}
		@Override
		public int compareTo(Point o) {
			int val = this.x - o.x;
			if(val == 0) {
				return this.y-o.y;
			}else
				return val;
		}
	}
	
	public static class point_compartor implements Comparator{

		@Override
		public int compare(Point o1, Point o2) {
			// TODO Auto-generated method stub
			return o1.y-o2.y;
		}
	}

'Java' 카테고리의 다른 글

Java String Class(String, StringBuffer, StringBuilder) 특징 및 차이 (2)	2020.07.09

# 유형 : 플로이드-와샬 알고리즘

# 플로이드 와샬 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제

***시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다는 점만 유의할것


package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p11404 {
	static int INF = 1000000000;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int arr[][] = new int[n+1][n+1];
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(i==j)
					continue;
				else
					arr[i][j] = INF;
			}
		}
		
		int m = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			arr[u][v] = Math.min(arr[u][v], val);
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				for(int k=1; k<=n; k++) {
					arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
				}
			}
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(arr[i][j]>=INF)
					System.out.print("0 ");
				else
					System.out.print(arr[i][j]+ " ");
			}System.out.println();
		}
	}
}

'백준' 카테고리의 다른 글

#백준_2261 가장 가까운 두 점 (0)	2020.01.13
#백준_1517 버블 소트 (0)	2020.01.13
백준_11657 타임머신 - Java 자바 (출력초과 수정완료) (0)	2020.01.11
#백준_1654 랜선 자르기 - Java (0)	2020.01.11
#백준_2805 나무 자르기 - Java (0)	2020.01.11

# 다익스트라 알고리즘은 어떠한 정점을 기준으로 잡고 다른 모든 정점으로의 최단 거리를 구하는 알고리즘이고, 플로이드 와샬은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘이다. 다익스트라는 가장 적은 비용을 가지는 간선을 하나씩 선택하여 알고리즘을 수행했다면, 플로이드 와샬은 거쳐가는 정점을 기준으로 알고리즘을 수행했다는 점이 특징이다.

다익스트라는 그리디 기법을 기반 / 플로이드 와샬은 다이나믹 프로그래밍 기반

플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다.

반복문 3개를 중첩하기 때문에, 시간 복잡도는 O(V^3)로 복잡하다.



public class floydwarshall {
	static int INF = 999999;
	public static void main(String[] args) {
		
		int arr[][] = {{0,   1,   INF, 4, 5},
                       {INF, 0,   3,   2, 1},
                       {1,   INF, 0,   5, 3},
                       {INF, INF, 4, 0, 2},
                       {4, INF, 1, 7, 0}};
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr.length; j++) {
				for(int k=0; k<arr.length; k++) {
					if(arr[j][k] > arr[j][i] + arr[i][k])
						arr[j][k] = arr[j][i] + arr[i][k];
				}
			}
		}
		
		for(int i=0; i<arr.length; i++) {
			for(int j=0; j<arr.length; j++) {
				System.out.print(arr[i][j]+ " ");
			}System.out.println();
		}
		
	}
}

'알고리즘' 카테고리의 다른 글

#알고리즘_벨만 포드(Bellman-Ford Algorithm) - Java (0)	2020.01.11
#알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java (0)	2020.01.09
#알고리즘_선형 탐색/이진 탐색 - Java (0)	2020.01.08
#알고리즘_신장 트리(Spanning Tree) (0)	2020.01.08
#알고리즘_프림(Prim Algorithm) - Java (0)	2020.01.08

uk's study

전체 글

#백준_7453 합이 0인 네 정수 - Java

'백준' 카테고리의 다른 글

#백준_1208 부분수열의 합 2 - Java

'백준' 카테고리의 다른 글

#백준_1261 알고스팟 - Java

'백준' 카테고리의 다른 글

#백준_2261 가장 가까운 두 점

'백준' 카테고리의 다른 글

#백준_1517 버블 소트

'백준' 카테고리의 다른 글

#자바_Comparable, Comparator

1. Comparable

2. Comparator

'Java' 카테고리의 다른 글

#백준_11404 플로이드 - Java

'백준' 카테고리의 다른 글

#알고리즘_플로이드 와샬(Floyd-Warshall Algorithm) - Java

'알고리즘' 카테고리의 다른 글

+ Recent posts

티스토리툴바