www.acmicpc.net/problem/2273

 

2273번: 줄 서기

첫째 줄에 N(1≤N≤256), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

www.acmicpc.net

키를 비교한 두 학생의 번호 u, v가 주어집니다.

d[u][v] : u가 v보다 앞에서야하는 경우

이는 방향그래프이며 인접행렬을 만들어주고 플로이드로 상대적인 키 정보를 구합니다.

 

그리고 이중for를 돌리면서 d[i][j] = true이고, d[j][i] = true인 것을 찾아줍니다.

d[i][j]=true이면 i가 j보다 앞에 있어야한다는 뜻인데

d[j][i]=true이면 j가 i보다 앞에 있어야한다는 뜻이므로 둘다 true면 모순입니다. 이때는 -1을 출력하고 리턴합니다.

 

확인이 끝났으면 왼쪽 경계 값(l = 1), 오른쪽 경계 값(r = N)으로 두고 1번학생부터 확인합니다.

d[i][j]=true이면 i보다 뒤에 있어야하는 학생이 1명 추가됩니다. => r--;

d[j][i]=true이면 i보다 앞에 있어야하는 학생이 1명 추가됩니다. => l++;

 

모든 학생을 확인하고 l r 을 출력합니다.

 

 

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
#include <iostream>
using namespace std;
 
bool d[257][257];
int N, M;
 
void func() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (d[i][k] && d[k][j]) d[i][j] = true;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (d[i][j] && d[j][i]) {
                cout << "-1\n";
                return;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        int l = 1;
        int r = N;
        for (int j = 1; j <= N; j++) {
            if (d[i][j]) r--;
            else if (d[j][i]) l++;
        }
 
        cout << l << ' ' << r << '\n';
    }
}
 
void input() {
    int u, v;
    cin >> N >> M;
    while (M--) {
        cin >> u >> v;
        d[u][v] = true;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > Floyd' 카테고리의 다른 글

boj 14938 서강그라운드  (0) 2021.03.24

www.acmicpc.net/problem/9205

 

9205번: 맥주 마시면서 걸어가기

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.

www.acmicpc.net

1번 정점 : 시작점

2번 ~ N + 1번 정점 : 편의점

N + 2번 정점 : 도착점

 

bfs와 플로이드 와샬 두 가지 방법을 이용할 수 있습니다.

 

먼저 bfs 풀이로는 N^2으로 각 정점들 사이의 거리가 1000이하인 간선만 그래프화 시켜줍니다.

그 다음 1번정점으로 시작하여 bfs로 인접한 모든 정점을 방문한 후에 N + 2번 정점을 방문하였는지 확인합니다.

N + 2번 정점을 방문 하였으면 happy, 방문 안했으면 sad를 출력합니다.

 

 

플로이드 풀이로는 N^2으로 각 정점들 사이의 거리가 1000이하면 dis[i][j] = true를 하여 간선체크를 해줍니다.

그 다음 플로이드를 사용하는데 i ~ k번을 지나갈 수 있고, k ~ j번을 지나갈 수 있으면 i ~ j번을 지나갈 수 있습니다.

따라서 dis[i][k] && dis[k][j]이면 dis[i][j] = true를 해줍니다.

dis[1][N+2] = true면 happy, false면 sad를 출력합니다.

 

bfs
플로이드 와샬

 

실행 시간은 bfs쪽이 좀 더 빨랐습니다.

 

 

[bfs]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> graph[] = new ArrayList[103];
    static boolean visit[] = new boolean[103];
    static int list[][] = new int[103][2];
    static int N;
 
    static void bfs() {
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(1);
        visit[1] = true;
        while (!dq.isEmpty()) {
            int x = dq.poll();
 
            for (int i = 0; i < graph[x].size(); i++) {
                int next = graph[x].get(i);
 
                if (visit[next])
                    continue;
 
                dq.add(next);
                visit[next] = true;
            }
        }
 
        if (visit[N + 2])
            sb.append("happy\n");
        else
            sb.append("sad\n");
    }
 
    static boolean getDis(int a[], int b[]) {
        return (Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1])) <= 1000 ? true : false;
    }
 
    static void func() {
        for (int i = 1; i <= N + 1; i++) {
            for (int j = i + 1; j <= N + 2; j++) {
                if (getDis(list[i], list[j])) {
                    graph[i].add(j);
                    graph[j].add(i);
                }
            }
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N + 2; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
    }
 
    static void init() {
        Arrays.fill(visit, false);
        for (int i = 1; i <= N + 2; i++) {
            graph[i] = new ArrayList<>();
        }
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
            init();
            func();
            bfs();
        }
        System.out.println(sb.toString());
    }
}
 cs

 

 

[플로이드 와샬]

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[][] = new int[103][2];
    static boolean dis[][] = new boolean[103][103];
    static int N;
 
    static int getDis(int x, int y, int tx, int ty) {
        return Math.abs(x - tx) + Math.abs(y - ty);
    }
 
    static void func() {
        for (int i = 1; i <= N + 1; i++) {
            for (int j = i + 1; j <= N + 2; j++) {
                if (getDis(list[i][0], list[i][1], list[j][0], list[j][1]) <= 1000) {
                    dis[i][j] = true;
                    dis[j][i] = true;
                }
            }
        }
 
        for (int k = 1; k <= N + 2; k++) {
            for (int i = 1; i <= N + 2; i++) {
                for (int j = 1; j <= N + 2; j++) {
                    if (dis[i][k] && dis[k][j])
                        dis[i][j] = true;
                }
            }
        }
 
        if (dis[1][N + 2])
            sb.append("happy\n");
        else
            sb.append("sad\n");
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N + 2; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
    }
 
    static void init() {
        for (int i = 1; i <= N + 2; i++)
            Arrays.fill(dis[i], false);
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        for (int t = 1; t <= tc; t++) {
            input();
            func();
            init();
        }
 
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > bfs' 카테고리의 다른 글

boj 14923 미로 탈출  (0) 2021.03.29
boj 17836 공주님을 구해라!  (0) 2021.03.26
boj 1600 말이 되고픈 원숭이  (0) 2021.03.24
boj 2589 보물섬  (0) 2021.03.16
boj 11559 Puyo Puyo  (0) 2021.02.26

www.acmicpc.net/problem/14938

 

14938번: 서강그라운드

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을

www.acmicpc.net

플로이드 와샬 알고리즘을 이용하여 각 정점에서부터의 최단거리를 모두 구해줍니다.

그리고 1 ~ N정점을 시작점으로 다른 정점과의 거리가 M 이하인 경우만 아이템 수를 더해줍니다.

다 더했으면 최댓값을 갱신해줍니다.

 

 

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
#include <iostream>
#include <algorithm>
#define INF 1000000000
using namespace std;
 
int dis[101][101], list[101];
int N, M, R;
 
void solve() {
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int sum = 0;
        for (int j = 1; j <= N; j++) {
            if (dis[i][j] > M) continue;
 
            sum += list[j];
        }
        ans = max(ans, sum);
    }
 
    cout << ans << '\n';
}
 
void func() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = INF;
        }
    }
}
 
void input() {
    int u, v, w;
    cin >> N >> M >> R;
    init();
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    while (R--) {
        cin >> u >> v >> w;
        dis[u][v] = w;
        dis[v][u] = w;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
    solve();
 
    return 0;
}
 cs

'algorithm > Floyd' 카테고리의 다른 글

boj 2273 줄 서기  (0) 2021.04.16

+ Recent posts

티스토리툴바