반응형

https://www.acmicpc.net/problem/2479

 

2479번: 경로 찾기

길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각각의 코드를 입력받아 str 배열에 저장합니다.

 

2. 각각의 코드들을 서로 비교하면서 다른 자릿수가 1개만 존재하는 쌍들로 list 배열을 만들어 저장합니다.

 

3. bfs를 이용하여 A부터 B까지 경로가 존재하면 경로를 저장해 해당 경로를 출력하고, 그렇지 않으면 -1을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#include<string>
 
using namespace std;
 
int N, K;
vector<int> list[1001];
int visited[1001];
string str[1001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> K;
 
    for (int i = 1; i <= N; i++) {
        cin >> str[i];
    }
 
    for (int i = 1; i < N; i++) {
        for (int j = i + 1; j <= N; j++) {
            int cnt = 0;
            for (int k = 0; k < K; k++) {
                if (str[i][k] != str[j][k]) {
                    cnt++;
                }
                if (cnt > 1) break;
            }
            if (cnt == 1) {
                list[i].push_back(j);
                list[j].push_back(i);
            }
        }
    }
 
    queue<pair<int, vector<int>>>q;
 
    int A, B;
    cin >> A >> B;
 
    q.push({ A,{} });
    visited[A] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().first;
        vector<int> route = q.front().second;
        q.pop();
 
        route.push_back(cur);
 
        if (cur == B) {
            for (auto& next : route) {
                cout << next << ' ';
            }
            return 0;
        }
 
        for (auto& next : list[cur]) {
            if (visited[next] != 1) {
                visited[next] = 1;
                q.push({ next,route });
            }
        }
    }
 
    cout << -1;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
[ 백준 ] 2463번 - 비용 (C++)  (0) 2023.08.23
[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 10216번 - Count Circle Groups (C++)  (0) 2023.08.19
반응형

https://www.acmicpc.net/problem/11403

 

11403번: 경로 찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!!

https://rudalsd.tistory.com/24?category=1064608 

 

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이

rudalsd.tistory.com

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int arr[101][101];
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][k] == 1 && arr[k][j] == 1) {
                    arr[i][j] = 1;
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20055번 - 컨베이어 벨트 위의 로봇 (C++)  (0) 2022.09.07
[ 백준 ] 21608번 - 상어 초등학교 (C++)  (0) 2022.09.06
[ 백준 ] 17471번 - 게리맨더링 (C++)  (0) 2022.09.04
[ 백준 ] 1003번 - 피보나치 함수 (C++)  (0) 2022.09.03
[ 백준 ] 16234번 - 인구 이동 (C++)  (0) 2022.09.02

+ Recent posts

티스토리툴바