https://www.welcomekakao.com/learn/courses/30/lessons/43163



단어의 철자를 바꿔가면서 목록에 있는 단어들 사이에서 차례로 변화가 일어날 수 있다는 것을 이용해서


인접행렬을 만들어준다.


초기 시작지점을 찾을 때, 단어를 바꾸고 시작하냐, 수정 없이 시작하냐를 따져준다.


목적 단어가 목록에 없으면 BFS를 수행할 필요도 없이 0을 반환해준다.



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
#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
 
int m[51][51], dis[51], st = -1, en = -1;
bool addOne = false;
queue<int> q;
void bfs(vector<string>& grp) {
    q.push(st);
    dis[st]++;
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            int cur = q.front();
            q.pop();
 
            for (int i = 0; i < grp.size(); i++) {
                if (m[cur][i] == 0 || dis[i] >= 0) continue;
                q.push(i);
                dis[i] = dis[cur] + 1;
                if (i == en) return;
            }
        }
    }
}
int solution(string src, string dst, vector<string> wrds) {
 
    int len = wrds[0].length();
 
    for (int i = 0; i < wrds.size(); i++) {
        dis[i] = -1;
        if (wrds[i] == src) { //시작 단어와 같은 단어가 목록에 존재
            st = i;
            addOne = false; //결과에 1 더해줄 필요가 없음
        }
        if (wrds[i] == dst) en = i;
 
        if (st == -1) { //시작 단어와 같은 단어가 목록에 없는 경우
            int dif = 0;
            for (int k = 0; k < len; k++) {
                if (wrds[i][k] != src[k]) dif++;
                if (dif > 1) break;
            }
            if (dif == 1) {
                st = i;
                addOne = true; //결과에 1을 더해준다. 시작부터 한번 바꾸고 시작했으니까
            }
        }
 
        //단어를 노드로 인접행렬 만들기
        for (int j = i + 1; j < wrds.size(); j++) {
            int dif = 0;
            for (int k = 0; k < len; k++) {
                if (wrds[i][k] != wrds[j][k]) dif++;
                if (dif > 1) break;
            }
            if (dif == 1) { //철자 하나 다를때만 연결
                m[i][j] = 1;
                m[j][i] = 1;
            }
        }
    }
 
    //목표 단어가 목록에 없으면 0 반환
    if (en != -1)
        bfs(wrds);
    else return 0;
 
    if (dis[en] != -1) { //바꿀 수 있으면
        if (!addOne)
            return dis[en];
        else
            return dis[en] + 1;
    }
    else
        return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

프로그래머스: 메뉴 리뉴얼 (C++)  (0) 2021.08.22
프로그래머스: 베스트앨범 (C++)  (0) 2019.10.30
프로그래머스: 네트워크 (C++)  (0) 2019.09.28
프로그래머스: 카펫 (C++)  (0) 2019.09.28
프로그래머스: 숫자 야구 (C++)  (0) 2019.09.27

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



모든 점을 방문할 수 있는지 확인하면 되는 문제이므로 bfs / dfs로 기본적으로 접근할 수 있다.


또한 n이 작기 때문에 플로이드 와샬도 가능하다. 가중치는 모두 1로 두면 되겠다.




이러한 문제를 풀 때 신경써줄 부분은, 자기 자신을 곧바로 방문할 수 있는지 확인하는 것이다.


이 문제에서는 노드1->노드1 이런식으로 곧바로 자기 자신을 방문할 수 없고, 1->2->3->1 이런식으로 사이클을 거쳐서 root(자기 자신)을 방문할 수 있다.


따라서 플로이드 와샬 알고리즘을 적용할 때, 비용을 무한대로 초기화 하는 과정에서, 자기 자신으로 가는 비용도 무한대로 초기화해주고 시작해야 한다.




비슷한 맥락으로, DFS로 문제를 풀이할 때, 보통 시작점을 방문처리하고 알고리즘을 시작한다.


하지만 시작점을 방문처리하고, 미방문한 지점을 이어서 방문하도록 알고리즘을 구현하면


1-> 2-> 3-> 1  이 과정에서, 마지막에 3->1을 방문할 수가 없다. 초기에 시작 지점인 1을 방문처리 했기 때문이다.


따라서 이것을 방지하기 위해서 시작지점을 방문처리하지 않는다. 3->1을 거쳐서 시작 지점에서 다시 for 문을 돌면 어짜피 갈 수 있는 곳이 없으므로 재귀를 탈출하게 된다.




1. DFS


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
#pragma warning(disable :4996)
#include<iostream>
using namespace std;
 
int m[101][101];
bool vis[101][101], chk[11];
int n, root;
void dfs(int cur) {
 
    for (int i = 0; i < n; i++) {
        if (m[cur][i] == 1 && !chk[i]) {
            chk[i] = true;
            dfs(i);
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    //cout << '\n';
 
    for (int i = 0; i < n; i++) {
        dfs(i); // i->i로 곧바로 갈 수 없으므로 시작점 방문처리 안 함
 
        //노드i에서 시작해서 방문할 수 있는 점들 표시
        for (int j = 0; j < n; j++) {
            if (chk[j]) cout << 1 << ' ';
            else cout << 0 << ' ';
        }
        cout << '\n';
 
        //초기화
        for (int i = 0; i < n; i++) 
            chk[i] = false;
        
    }
 
    return 0;
}
 
cs




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
#include<iostream>
#include<algorithm>
#define INF 100000
using namespace std;
 
int n; //정점 개수
int m[101][101];
 
void FW() { //플로이드 와샬
    for (int k = 0; k < n; k++)
        for (int j = 0; j < n; j++)
            for (int i = 0; i < n; i++)
                m[i][j] = min(m[i][j], m[i][k] + m[k][j]);
}
int main(void) {
 
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
        
            cin >> m[i][j];
            if (m[i][j] == 0 ) m[i][j] = INF;
            //자기 자신으로 갈 수 없다고 봄 -> 자기 자신으로 가는 비용도 무한초기화
        }
    
    FW();
 
    //cout << '\n';
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (m[i][j] == INF) //비용이 무한 -> 방문할 수 없다는 의미
                cout << 0 << ' ';
            else
                cout << 1 << ' ';
        }
        cout << '\n';
    }
    
    
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2644번: 촌수계산 (C++)  (0) 2019.09.25
백준 11724번: 연결 요소의 개수 (C++)  (0) 2019.09.25
백준 1152번: 단어의 개수 (C++)  (0) 2019.09.20
백준 2193번: 이친수 (C++)  (0) 2019.09.19
백준 1003번: 피보나치 함수 (C++)  (0) 2019.09.19

https://www.welcomekakao.com/learn/courses/30/lessons/42892



순회는 간단한 부분이기 때문에, 사실 관건은 좌표를 이용해서 트리를 어떻게 만들 것이냐이다.


기본적으로 위에서부터, root를 시작으로 아래로 채워갈 것이기 때문에, 입력받는 좌표를 y값 내림차순으로 정렬한다. y좌표가 동일한 경우 x좌표 오름차순으로 정렬해서, 왼쪽 자식부터 확인할 수 있도록 한다.


정렬을 할 때, 아무런 처리를 해주지 않고 정렬하게 되면, 본인이 원래 몇 번째 인덱스였는지 잃어버리기 때문에, 이후에 순회를 할 수가 없다.


따라서 입력을 받을 당시에, 본인의 인덱스를(노드 번호) 갖고 있도록 처리를 해주어야 한다.



본인은 구조체를 이용했고, 사실 벡터에 그냥 인덱스를 추가해줘도 상관이 없을 것 같다.



트리를 만들 때는, 링크드리스트의 형태를 취해서 만드는 것도 가능하고, 배열의 인덱스를 루트로 해서 하는 방법도 가능하다.


본인은 후자로 구현했다.



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
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
 
struct Node {
    int idx, l = 0, r = 0, x, y;
}b[10001];
struct move {
    int l, r;
}m[10001];
bool cmp(Node a, Node b) {
    if (a.y > b.y) return true;
    else if (a.y < b.y) return false;
    else {
        return a.x < b.x;
    }
}
int num;
void makeTree(int root) {
 
    for (int i = 2; i <= num; i++) {
        int cur = root;
        while (1) {
            if (b[i].x < b[cur].x) {
                if (b[cur].l == 0) {
                    b[cur].l = i;
                    break;
                }
                else
                    cur = b[cur].l;
            }
            else {
                if (b[cur].r == 0) {
                    b[cur].r = i;
                    break;
                }
                else
                    cur = b[cur].r;
            }
        }
    }
}
vector<int> pre;
void preOrder(int cur) {
    if (cur == 0) return;
    pre.push_back(cur);
    preOrder(m[cur].l);
    preOrder(m[cur].r);
}
vector<int> pos;
void postOrder(int cur) {
    if (cur == 0) return;
    postOrder(m[cur].l);
    postOrder(m[cur].r);
    pos.push_back(cur);
}
vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
    vector<vector<int>> answer;
    num = nodeinfo.size();
 
    for (int i = 1; i <= nodeinfo.size(); i++) {
        b[i].x = nodeinfo[i-1][0];
        b[i].y = nodeinfo[i-1][1];
        //cout << nodeinfo[i - 1][0] << ' ' << nodeinfo[i - 1][1] << '\n';
        b[i].idx = i;
    }
 
    sort(b+1, b + num+1, cmp); //1. y좌표 큰순, 2. x좌표 작은순
    
    makeTree(1); // root의 노드 번호
    
    for (int i = 1; i <= num; i++) {
        m[b[i].idx].l = b[b[i].l].idx;
        m[b[i].idx].r = b[b[i].r].idx;
    }
 
    preOrder(b[1].idx);
    postOrder(b[1].idx);
 
    answer.push_back(pre);
    answer.push_back(pos);
    return answer;
}
 
int main(void) {
    vector<vector<int>> nodeinfo;
    nodeinfo = { {5,3},{11,5}, {13,3}, {3,5}, {6,1}, {1,3}, {8,6}, {7,2}, {2,2} };
    solution(nodeinfo);
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글

2017 카카오 블라인드 테스트 1차: 비밀지도 (C++)  (0) 2019.08.23
카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
카카오 2018 블라인드 테스트: 실패율 C++  (0) 2019.08.19
카카오 2018 블라인드 테스트: 오픈채팅방 C++  (0) 2019.08.19
프로그래머스: 모의고사 (C++)  (0) 2019.07.09

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


그래프 정보를 배열로 받아주고, DFS를 돌려주면 된다.


DFS를 실행할 때, 방문한 지점을 다시 방문하는 것이 base condition이므로, DFS가 끝날 때 마다 사이클의 개수가 하나씩 늘어난다.


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
#include<iostream>
#include<vector>
using namespace std;
int v[1002];
bool vis[1002];
 
void dfs(int cur) {
    if (vis[cur]) return; //이미 방문한 곳을 재방문 했다는 건 사이클이라는 뜻
 
    vis[cur] = true;
    int next = v[cur];
    dfs(next);
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        
        for (int i = 1; i <= n; i++) 
            cin >> v[i];
        
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && v[i] != 0) {
                cnt++;
                dfs(i);
            }
        }
        cout << cnt << '\n';
 
        for (int i = 1; i <= n; i++) 
            vis[i] = false;
        
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14

+ Recent posts

티스토리툴바