반응형

문제출처

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


문제풀이

1
2
3
4
5
6
7
8
9
10
11
/**
 * O(2^(n*n))의 시간복잡도를 가지는데 n이 10인경우 2^100의 시간복잡도가 된다.
 * 때문에 N-Queen과 같이 행을 기준으로 모든 방법을 탐색하는 경우 시간초과가 된다.
 * 이 문제는 전체 탐색을 하면 안되는 문제이다. 여기서 풀이를 못했는데 다른 분들의 풀이를 보고
 * 독립사건으로 나누었습니다. 즉, 실제 체스판을 보면 흰색과 검정색이 교차로 있는데 비숍은 대각선만
 * 움직이기 때문에 처음 흰색칸에 존재한다면 흰색판안에서만 돌아다닐 수 있고
 * 검은색판에는 영향을 미치지 않습니다. 즉 흰색판과 검은색판은 비숍에 대해 독립적인 것이죠.
 * 이 문제를 나누어서 흰색판과 검은색판을 서로 나누어 결과를 더하면 각각 O(2^25)의 시간복잡도를 가지며
 * 이 값은 약 6~7천만 사이입니다. 비록 완전하게 풀지는 못한 문제이지만 새로운 풀이방법을 알게 된문제.
 * 시간초과가 나고 어떻게 분할해서 풀이할지 아이디어가 생각이 안났는데 아쉽다 ㅠㅠ
 */
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
#include <iostream>
#include <algorithm>
#define MAX 10
using namespace std;
int n,result[2];
int map[MAX][MAX];
bool visit[2][2*MAX];
 
void solve(int x, int y, int cnt, int color) {
    result[color]=max(result[color],cnt);
    if(x>=n)    return;
    if(y>=n) {
        x++;
        y=color^(x%2);
    }
    if(map[x][y] && !visit[0][x+y] && !visit[1][n-(x-y)]) {
        visit[0][x+y]=visit[1][n-(x-y)]=1;
        solve(x,y+2,cnt+1,color);
        visit[0][x+y]=visit[1][n-(x-y)]=0;
    }
    solve(x,y+2,cnt,color);
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin>>map[i][j];
        }
    }
    solve(0,0,0,0);
    solve(0,1,0,1);
    cout<<result[0]+result[1];
    return 0;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[BOJ 3056] 007  (0) 2019.01.31
[BOJ 1102] 발전소  (0) 2019.01.30
[Programmers] 정렬 - 가장큰수  (0) 2019.01.28
[BOJ 7562] 나이트의 이동  (0) 2019.01.28
[BOJ 9663] N-Queen  (0) 2019.01.28
반응형

문제출처

https://programmers.co.kr/learn/courses/30/lessons/42746


문제풀이

1
2
3
4
5
6
/**
 * 직감적으로 그냥 큰수가 앞에오면 된다고 생각할 수 있지만 10, 9 와같은 케이스에서 바로 걸린다.
 * 109보다 910이 더 크기 때문이다. string을 사용하여 10과 9를 붙인것과 9와 10을 붙인것을 비교해서 
 * 정렬한다면 쉽게 풀수 있는 문제입니다. 예를들어 [34, 345]가 있다면 34345와 34534를 비교해서 정렬을 하는데
 * 34534가 더 크므로 [345,34]와 같이 정렬될 것입니다. 또한 0일경우 예외사항으로 빼줘야 하는 것도 중요한 문제입니다.
 */
cs


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
bool comp(string &a, string &b) {
    return a+b > b+a ? true : false;
}
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> tmp;
    for(int i=0; i<numbers.size(); i++)
        tmp.push_back(to_string(numbers.at(i)));
    sort(tmp.begin(), tmp.end(), comp);
    for(string str : tmp) answer+=str;
    if(answer[0]=='0')  answer="0";
    return answer;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[BOJ 1102] 발전소  (0) 2019.01.30
[BOJ 1799] 비숍  (0) 2019.01.29
[BOJ 7562] 나이트의 이동  (0) 2019.01.28
[BOJ 9663] N-Queen  (0) 2019.01.28
[BOJ 2098] 외판원 순회  (0) 2019.01.28
반응형

문제출처

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


문제풀이

1
2
3
4
5
6
7
/**
 * 문제가 몇번만에 이동할 수 있는지 알아내는 문제입니다. 즉, 최소값을 구하는 문제이므로 bfs를 사용했습니다.
 * visit배열을 쓰는 대신 map을 -1로 재선언 해주어 방문을 하면 0을 넣어줬습니다.
 * visit배열을 사용한다면 bool visit[MAX][MAX]를 선언한뒤 조건에 추가해주면 됩니다.
 * 좌표가 out of bound이면 탐색을 하지 않고 방문을 하지 않은 상태 즉 map[x][y]==-1이라면
 * bfs로 다시 방문을 해주면서 카운트하면 되는 문제입니다.
 */
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
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n,destx, desty;
int dx[]={-2,-2,-1,-1,1,1,2,2};
int dy[]={-1,1,-2,2,-2,2,-1,1};
vector<vector<int> > map;
 
void bfs(int x, int y) {
    queue<pair<int, int> > q;
    q.push(make_pair(x,y));
    map[x][y]=0;
    while(!q.empty()) {
        x=q.front().first;
        y=q.front().second;
        q.pop();
        for(int i=0; i<8; i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<0 || ny<0 || nx>=n || ny>=n)  continue;
            if(map[nx][ny]==-1) {
                q.push(make_pair(nx, ny));
                map[nx][ny]=map[x][y]+1;
                if(nx==destx && ny==desty) {
                  return;
                }
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int tc;
    cin>>tc;
    for(int i=0; i<tc; i++) {
        int x,y;
        cin>>n;
        cin>>x>>y>>destx>>desty;
        map=vector<vector<int> >(n, vector<int>(n,-1));
        bfs(x,y);
        cout<<map[destx][desty]<<endl;
    }
    return 0;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[BOJ 1799] 비숍  (0) 2019.01.29
[Programmers] 정렬 - 가장큰수  (0) 2019.01.28
[BOJ 9663] N-Queen  (0) 2019.01.28
[BOJ 2098] 외판원 순회  (0) 2019.01.28
[CodeForce] 158A - Next Round  (0) 2019.01.25
반응형

문제출처

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


문제풀이

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 퀸은 행,열,대각방향으로 공격할 수 있는 기물입니다. 따라서 각 행, 열에는 퀸이 오직 1개만 위치할 수 있습니다.
 * 대각선은 가로의차이가 세로의 차이와 같으면 대각방향에 위치할 수 없는 것으로 판단할 수 있습니다.
 * => 행렬을 그린뒤 row+col의 값을 모두 그려보면 왜 그런지 알 수 있습니다. (row+col)의 값이 대각성분끼리 같습니다.
 * 탐색할 수 있는 경우를 모두 탐색하되 유망한지를 참조하여 탐색합니다.
 * 1차원 배열로 문제를 풀이하는게 처음에 이해가 가지 않았는데 map[0]=1 이라면 0행 1열에 퀸이 위치하는 것을 뜻합니다.
 * 즉, isPromising 함수에서 map[i]와 map[cur]이 같은지 비교하는 것은 같은 열에 위치하는지 체크하는 것을 뜻하며
 * 위에서 설명한 것처럼 대각성분도 체크해주어 현 상태가 유망한지 판단하는 것입니다. 행과 같은 경우는 dfs를 사용하기
 * 때문에 따로 체크를 하지 않고 유망할 경우 다음행을 탐색하는 방법으로 풀이하면 되는 문제입니다.
 * 처음 백트래킹 개념을 이해하지 못해서 직접 풀지는 못한 문제이지만 풀이를 보고 어느정도 백트래킹에대해 알 수 있었던
 * 문제였습니다.
 */
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
#include <iostream>
#include <cmath>
#define MAX 16
 
using namespace std;
int n,result;
int map[MAX];
 
bool isPromising(int cur) {
    for(int i=0; i<cur; i++) {
        if(map[i] == map[cur] || abs(map[cur]-map[i]) == abs(cur-i)) {
            return false;
        }
    }
    return true;
}
 
void solve(int cur) {
    if(cur==n) {
        result++;
    }
 
    for(int i=0; i<n; i++) {
        map[cur] = i;
        if(isPromising(cur)) {
           solve(cur+1);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    solve(0);
    cout<<result;
    return 0;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[Programmers] 정렬 - 가장큰수  (0) 2019.01.28
[BOJ 7562] 나이트의 이동  (0) 2019.01.28
[BOJ 2098] 외판원 순회  (0) 2019.01.28
[CodeForce] 158A - Next Round  (0) 2019.01.25
[CodeForce] 71A - Way Too Long Words  (0) 2019.01.25
반응형

문제출처

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


문제풀이

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
/**
 * n이 16까지 주어지는데 모든 경우의 수는 16!로 굉장히 큰 것을 예상할 수 있습니다.
 * => 처음 1번도시를 방문하고 다음도시를 방문할 수 있는 경우의 수는 n-1이며 그 다음은 n-2이기 때문에 n!의 시간복잡도를 가집니다.
 * 처음에 dfs와 같은 방법으로 전체탐색을 수행하려 했지만 시간제한이 1초여서 다른 방법을 생각하던 중
 * DP를 사용하면 해결될듯 하여 해당 주제인 비트마스크와 DP를 사용했습니다.
 *
 * 비트마스크 visit로 사용
 * 만약 4개의 도시중 방문한 도시가 없다면 0000으로 표현할 수 있습니다. 1번 도시를 방문한 경우 0001
 * 2번도시를 방문한 경우는 0010 이와 같이 1번 3번도시를 방문했다면 0101으로 표현할 수 있습니다.
 * 때문에 모든 도시를 방문한 경우 1111로 나타낼수 있습니다.
 * 여기서 중요한 것은 하나하나의 비트가 0이면 방문하지 않은 상태를 뜻하고 1이면 방문한 것을 의미합니다.
 *
 * 그럼 방문여부를 체크할때는 어떻게 할까 고민해 봐야한다. 예제에서 볼 수 있듯이 1->3의 값과 3->1의 가중치가 다릅니다.
 * 즉, 현재 출발도시도 중요한 영향을 미치며 방문여부도 값에 영향을 미치는 것을 알 수 있습니다.
 * 이를 통해 dp배열의 구조를 생각할 수 있습니다. dp[현재도시][방문한도시]와 같이 표현할 수 있습니다.
 * 예를 들면 1,2,3번 도시를 방문했고 현재 3번도시에 위치한 경우 최소거리를 dp[3][0111](dp[3][7])로 나타낼 수 있습니다.
 * 여기서 레퍼런스 변수 &ret을 사용했는데 dp배열을 사용해도 문제없습니다. 레퍼런스 변수는 dp배열의 인덱스값을 확실하게 참조할 수 있는
 * 장점이 있습니다. 레퍼런스 변수 자체가 참조하는 주소를 기억하기 때문에 더 안정적이라고 하네요.
 * 이 문제는 0번도시, 4번도시 아무도시에서 시작해도 항상 같은 값을 가집니다. 왜냐하면 사이클이기 때문이죠.
 * 만약 경로가 있다는 가정하에 1->2->3->4->1 의값은 2->3->4->1->2 의 값과 같습니다. 2의 왼쪽은 1 // 2의오른쪽은 3 이런식으로 비교하면
 * 사이클이므로 값이 같다는 것을 알 수 있습니다. 때문에 저는 0번도시에서 시작을 하는 것으로 풀이를 시작했습니다.
* (다시 한번 강조하지만 어떤 도시든지 상관이 없습니다.)
 *
 * INF값을 0x7fffffff값을 주었는데 이경우 시간초과가 떴습니다. 왜 시간초과인지는 모르겠지만 1만 더해도 int범위를 벗어나기 때문에
 * 문제가 있을것이라 생각하고 10억이 넘는값으로 수정하니 맞았습니다.
 */
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
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAX 16
 
using namespace std;
 
int n;
int map[MAX][MAX];
int dp[MAX][1<<MAX];
 
int tsp(int cur, int visit) {
    //방문한 곳은 재방문하지 않았으므로 다시 원점으로 돌아오는 가중치를 return해줘서 더해준다.
   if(visit == (1<<n)-1)
       return (map[cur][0]>0) ? map[cur][0] : INF;
   int &ret=dp[cur][visit];
   if(ret>0)   return ret;
   ret=INF;
   for(int i=0; i<n; i++) {
       if(!(visit & (1<<i)) && map[cur][i]>0) {
           ret=min(ret, tsp(i, visit|(1<<i)) + map[cur][i]);
       }
   }
   return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    cin>>n;
    for(int i=0; i<n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    cout<<tsp(0,1)<<endl;
    return 0;
}
 
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[BOJ 7562] 나이트의 이동  (0) 2019.01.28
[BOJ 9663] N-Queen  (0) 2019.01.28
[CodeForce] 158A - Next Round  (0) 2019.01.25
[CodeForce] 71A - Way Too Long Words  (0) 2019.01.25
[BOJ 10163] 색종이  (0) 2019.01.24
반응형

문제풀이

영어 해석을 하면 풀수 있는 문제. k번째 선수보다 높은 점수를 가진 사람이 다음라운드로 진출할 수 있다.


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std;
// http://codeforces.com/problemset/problem/158/A
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,k,result=0;
    vector<int> scores;
    cin>>n>>k;
    int score;
    for(int i=0; i<n; i++) {
        cin>>score;
        scores.push_back(score);
    }
    for(int i=0; i<n; i++) {
        if(scores[i]>=scores[k-1] && scores[i]>0)   result++;
    }
    cout<<result<<endl;
    return 0;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[BOJ 9663] N-Queen  (0) 2019.01.28
[BOJ 2098] 외판원 순회  (0) 2019.01.28
[CodeForce] 71A - Way Too Long Words  (0) 2019.01.25
[BOJ 10163] 색종이  (0) 2019.01.24
[BOJ 1697] 숨바꼭질  (0) 2019.01.23
반응형

처음으로 코드포스 문제를 풀어봤다. 영어로 문제가 되있으니 처음에 엄청 쫄았는데 간단했다. 코드포스와 백준을 이제 같이 풀어나가야겠다. 단순 string을 조작하는 간단한 문제입니다.


소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <string>
// http://codeforces.com/problemset/problem/71/A
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int tc;
    cin>>tc;
    string str;
    while(tc--) {
        cin>>str;
        if(str.length()>10) cout<<str[0]<<str.length()-2<<str[str.length()-1]<<endl;
        else    cout<<str<<endl;
    }
    return 0;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[BOJ 2098] 외판원 순회  (0) 2019.01.28
[CodeForce] 158A - Next Round  (0) 2019.01.25
[BOJ 10163] 색종이  (0) 2019.01.24
[BOJ 1697] 숨바꼭질  (0) 2019.01.23
[BOJ 1325] 효율적인 해킹  (0) 2019.01.23
반응형

문제출처

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


문제풀이

1
2
3
4
5
/**
 * 복잡한 알고리즘 없이 단순 구현해 주면 되는 문제입니다.
 *  map에 input을 넣을때 색종이를 구분하면서 넣어주는데 기존에 있었던 공간에
 *  다른 색종이가 덮을 경우 기존 색종이는 보이지 않으므로 새로운 색종이 번호를 넣어주면 됩니다.
 */
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
#include <iostream>
#define MAX 101
using namespace std;
int n;
int area[MAX], map[MAX][MAX];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    int x,y,w,h;
    for(int cnt=1; cnt<=n; cnt++) {
        cin>>x>>y>>w>>h;
        for(int i = y; i < y + h; i++) {
            for (int j = x; j < x + w; j++) {
                map[j][i] = cnt;
            }
        }
    }
    for(int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            area[map[i][j]]++;
        }
    }
    for(int i=1; i<=n; i++) {
        cout<<area[i]<<endl;
    }
    return 0;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[CodeForce] 158A - Next Round  (0) 2019.01.25
[CodeForce] 71A - Way Too Long Words  (0) 2019.01.25
[BOJ 1697] 숨바꼭질  (0) 2019.01.23
[BOJ 1325] 효율적인 해킹  (0) 2019.01.23
[BOJ 10039] 평균점수  (0) 2019.01.22
반응형

문제출처

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


문제풀이

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
/**
 * DFS문제인지 BFS문제인지 구분하기!
 *
 * bfs
 * 가장 최단 경로를 구하고 싶을때 사용한다.(출발->도착)
 * 즉, 초기상태로부터 목표값까지의 최소 횟수를 구하고 싶을때 사용한다.
 *
 * dfs
 * 모든 조건(가능성)을 탐색할때 사용한다.
 * 즉, 어떤 방법이 가장 좋은 방법인지 알고싶을때 사용
 *
 * bfs와 dfs 모두 사용
 * 그래프 상 끊어진 연결이 없는지 확인하고자 할때 두가지 모두 사용가능하다.
 * 즉, 주어진 곳에서 다른 곳으로 도달할 수 있는지 알고 싶을때 사용한다.
 */
 
/**
 * 위 설명을 보면 최단 거리, 최소횟수는 BFS를 이용해야 하는 것을 알 수 있습니다.
 * 하지만 저는 몰랐어요 ㅠㅠ 저내용을 ㅠㅠ DFS로 풀이하다 무한루프에 빠져 프로그램이 죽어 BFS로 풀이하였습니다.
 * 문제 자체는 간단합니다. 현재 위치에서 목표 위치로 이동하는데 최소카운트를 출력하는 문제입니다.
 * bfs로 풀이하기 위해 큐를 하나 생성하는데 큐의 현재위치와 현재 큐에서 얼만큼 움직여야 하는지를 알기 위해 pair로 선언해줍니다.
 * 방문할 때마다 몇번만에 해당 위치에 도착했는지 카운트를 해주는 것입니다.(문제의 키포인트!)
 * 즉, 2에서 5를 가기 위해서 2*2를 통해 4가 되었으면 4번 위치의 카운트는 1입니다.
 * 이후 4->5로 가기위해 4+1로 5가 되면 5의 카운트는 1+1이 되어 2가 되겠죠.
 */
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
#include <iostream>
#include <queue>
#define MAX 100001
using namespace std;
int n,k,result;
bool visit[MAX];
int dx[]={-1,0,1};
void bfs(int s) {
    queue<pair<int, int> > q;
    q.push(make_pair(s,0));
    visit[s]=1;
    while(!q.empty()) {
        int x=q.front().first;
        int cnt=q.front().second;
        q.pop();
        if(x==k) {
            result=cnt;
            return;
        }
        for(int i=0; i<3; i++) {
            int nx;
            if(dx[i]==0)    nx=x*2;
            else    nx=x+dx[i];
            if(nx<0 || nx>=MAX || visit[nx]) continue;
            q.push(make_pair(nx, cnt+1));
            visit[nx]=1;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    bfs(n);
    cout<<result;
    return 0;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[CodeForce] 71A - Way Too Long Words  (0) 2019.01.25
[BOJ 10163] 색종이  (0) 2019.01.24
[BOJ 1325] 효율적인 해킹  (0) 2019.01.23
[BOJ 10039] 평균점수  (0) 2019.01.22
[BOJ 2468] 안전영역  (0) 2019.01.22
반응형

문제출처

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


문제풀이

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 모든 노드를 탐색하고, 탐색 가능한 최댓값을 구하는 문제입니다.
 * A가 B를 신뢰할 경우, B를 해킹하면 A도 해킹이 가능하다라는 설명이 요점입니다.
 * 즉, A가 B를 신뢰한다는 것을 다르게 말하면, B → A 로 연결된 방향 그래프인것이죠.
 * 
* 풀이한 순서를 설명드리면 아래와 같습니다.
* 먼저 입력을 받을때 신뢰 관계를 network에 저장합니다.
 * 이후 컴퓨터 개수가 n개이기 때문에 bfs를 n번 호출하여 해킹가능한 최대 컴퓨터를 구합니다.
 * 해킹가능한 최대 결과값이 같은 컴퓨터가 존재할 수 있으므로 결과 벡터를 생성해 결과값을 저장합니다.
 * 이때 가장 큰 값을 카운트 한 값과 비교하여 같으면 결과벡터에 추가를 하고,
 * 카운트 값이 크면 결과벡터를 초기화 한후 push를 합니다.
 * 조금만 생각해 보면 알 수 있는데, 최대 컴퓨터를 구하는 것이므로 새로운 최대 컴퓨터가 있다면 이전 결과는 모두 필요가 없기 때문입니다.
 * 생각보다 어려웠던 문제인데 bfs말고 dfs로도 풀이가 가능하니 최대한 빨리 dfs로 풀이하고 업데이트 하겠습니다.
 */
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
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n,m,maxValue;
vector<vector<int> > network;
vector<int> result;
bool visit[10001];
void bfs(int s) {
    queue<int> q;
    q.push(s);
    visit[s]=1;
    int cnt=0;
    while(!q.empty()) {
        int src=q.front();
        q.pop();
        for(int i=0; i<network[src].size(); i++) {
            int dest=network[src][i];
            if(!visit[dest]) {
                visit[dest]=1;
                q.push(dest);
                cnt++;
            }
        }
    }
    if(maxValue<cnt) {
        maxValue=cnt;
        result.clear();
        result.push_back(s);
    } else if(maxValue==cnt) {
        result.push_back(s);
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    network.resize(n+1);
    int src,dest;
    for(int i=0; i<m; i++) {
        cin>>src>>dest;
        network[dest].push_back(src);
    }
    for(int i=1; i<=n; i++) {
        memset(visit, 0, sizeof(visit));
        bfs(i);
    }
    sort(result.begin(), result.end());
    for(int i=0; i<result.size(); i++) {
        cout<<result[i]<<" ";
    }
    return 0;
}
cs


반응형
저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

[BOJ 10163] 색종이  (0) 2019.01.24
[BOJ 1697] 숨바꼭질  (0) 2019.01.23
[BOJ 10039] 평균점수  (0) 2019.01.22
[BOJ 2468] 안전영역  (0) 2019.01.22
[BOJ 2661] 좋은 수열  (0) 2019.01.21

+ Recent posts

티스토리툴바