<링크>

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


<소스코드>

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
#include<stdio.h>
#include<vector>
using namespace std;
int pan[101][101];
void check(int x, int y, int d, int g)
{
    vector<int> v;
    v.push_back(d);
    for (int i = 0; i < g; ++i)
    {
        int size = v.size();
        for (int j = size - 1; j >= 0; --j)
        {
            int dir = v[j];
            int toDir = (dir + 1) % 4;
            v.push_back(toDir);
        }
    }
    int size = v.size();
    pan[x][y] = 1;
 
    for (int i = 0; i < size; ++i)
    {
 
        int dir = v[i];
        switch (dir)
        {
        case 0:++x; break;
        case 1:--y; break;
        case 2:--x; break;
        case 3:++y; break;
        }
        pan[x][y] = 1;
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    while (N--)
    {
        int x, y, d, g;
        scanf("%d%d%d%d", &x, &y, &d, &g);
        check(x, y, d, g);
    }
    int ans = 0;
    for (int x = 0; x<100; ++x)
        for (int y = 0; y <100; ++y)
        {
            if (pan[x][y] && pan[x + 1][y] && pan[x][y + 1] && pan[x + 1][y + 1])
                ++ans;
        }
    printf("%d", ans);
}
 
cs


<풀이>

그림처럼 이전세대의 선분 하나랑 다음세대의 선분 한쌍이 각각 관계가 있다.


시작점부터의 방향만을 리스트로 나타내면 다음과 같다. 

잘 보면 규칙성을 발견할 수 있다. 

기존 세대의 방향 맨 끝부터 봤을때 기존 방향에서 왼쪽으로 90' 꺾은 방향으로 다음세대의 방향이 결정된다.

①↑에서 ←

②←에서↓

③↑에서 ←

④→에서↑

이런 규칙으로 변한다. 근데 문제에서도 친절하게


  • 0: x좌표가 증가하는 방향 (→)
  • 1: y좌표가 감소하는 방향 (↑)
  • 2: x좌표가 감소하는 방향 (←)
  • 3: y좌표가 증가하는 방향 (↓)

라고 되어있기 때문에 다음방향 = (이전방향+1)%4 이 된다.

이런식으로 K세대까지의 방향만을 쫙 만들어놓은 후

시작점부터 해당좌표에 체크해준다.


저작자표시

'알고리즘 풀이 > 시뮬레이션' 카테고리의 다른 글

백준 14890 경사로 :: 들짐승  (0) 2018.07.22
백준 14499 주사위굴리기 :: 들짐승  (0) 2018.07.22
백준 3190 뱀 :: 들짐승  (0) 2018.07.22
백준 12100 2048(Easy) :: 들짐승  (0) 2018.07.22

<링크>

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


<소스코드>

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
#include<cstdio>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
vector<P> h,c,a; // 집, 치킨집, 남겨둘 치킨집
int N, M;
int ans = 1e9;
void check(vector<P> &a)
{
    if (a.size() == 0)
        return;
    int sum = 0;
    for (P i : h)
    {
        int m = 1e9;
        for (P j : a)
            m = min(m, abs(i.first - j.first) + abs(i.second - j.second));
        sum += m;
    }
    ans = min(ans, sum);
}
void recur(int i, int len)
{
    if (len <= M)
        check(a);
    if (i == c.size()||len>M)
        return;
    a.push_back(c[i]);
    recur(i + 1, len + 1);
    a.pop_back();
    recur(i + 1, len);
}
int main()
{
    scanf("%d%d", &N, &M);
    for(int i=0;i<N;++i)
        for (int j = 0; j < N; ++j)
        {
            int n;
            scanf("%d", &n);
            if (n == 1)
                h.push_back({ i,j });
            if (n == 2)
                c.push_back({ i,j });
        }
    recur(0,0);
    printf("%d", ans);
}
 
cs


<풀이>

1. 집 좌표 리스트, 치킨집 좌표 리스트를 미리 준비해둔다.

2. 재귀함수를 이용해서 치킨집 조합을 만든다.

i번째 치킨집을 포함하면 a벡터에넣고 재귀호출, 안하면 a.pop_back()으로 뺀 후 재귀호출하고

현재까지 찍은 치킨집 개수가 M개 이하이면 check()함수에 a벡터를 던져준다.

찍은 치킨집 개수가 M개를 넘어가거나 i가 총 치킨집 개수를 넘어가면 return한다.


3. chek()함수에는 내가 찍은 치킨집들의 좌표가 넘어오기 때문에 집 하나당, 찍힌 치킨집 전부를 보며 최솟값을 찾아 더해준다.

모든 집들에 대해 반복해서 더하면 찍은 치킨집들로 만든 도시의 치킨거리가 나온다.

이 값을 보고 답을 갱신한다.

저작자표시

'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글

백준 1107 리모컨  (2) 2018.07.26
KOITP 고장난시계  (0) 2018.07.23
백준 1421 나무꾼 이다솜 ::들짐승  (0) 2018.07.22
백준 14888 연산자 끼워넣기 :: 들짐승  (0) 2018.07.22

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int visit[1001];
vector<pair<int, int>> adj[1001];
priority_queue<pair<int, int>> q;//오는비용,노드
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    while (M--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    q.push({ 0,1 });
    int ans = 0;
    while (!q.empty())
    {
        int cost = q.top().first;
        int node = q.top().second;
        q.pop();
        if (visit[node])
            continue;
        visit[node] = 1;
        ans += -cost;
    
        for (pair<int, int> p : adj[node])
        {
            int toCost = p.second;
            int toNode = p.first;
            q.push({ -toCost,toNode });
 
        }
    }
    printf("%d", ans);
}
cs


<풀이>

prim알고리즘을 적용했으며 priority_queue를 이용했다.

prim알고리즘은 greedy하게 현재 선택한 노드들에서 퍼져나갈 수 있는 간선들 중 가장 적은 비용의 간선을 택한다.

처음에 {0,1}을 넣어서 1번노드까지가는 비용 0을 넣어놓고

연결되어있으면 다 priority_queue에 넣어준다.

큐에 들어있는 쌍들은 {해당노드까지 가는 비용, 노드}인데 가장 작은값이 맨위에 올라와야하기 때문에 음수를 곱했다.

한번 방문한 노드는 또 볼필요없으므로 visit배열로 체크했다.

priority_queue의 맨위에는 현재 갈수있는 가장 가까운 정점이 떠올라와있기 때문에 선택하고, 해당 노드로 인해 추가되는 간선들을 다시 큐에 넣어주면 된다.


저작자표시

<링크>

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


<소스코드>

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<stdio.h>
#include<vector>
#include<queue>
using namespace std;
vector<int> adj[32001];
queue<int> q;
int indegree[32001];
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    while (M--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        ++indegree[b];
    }
    for (int i = 1; i <= N; ++i)
        if (indegree[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int c = q.front();
        printf("%d ", c);
        q.pop();
        for (int i : adj[c])
        {
            --indegree[i];
            if (indegree[i] == 0)
                q.push(i);
        }
    }
}
cs


<풀이>

차수를 기록하고 차수가 0인애들을 싹 큐에 집어넣는다.

큐에서 하나씩 빼면서 그 노드와 연결된 애들의 차수를 줄여주고, 차수가 0이되면 금마를 큐에 집어넣는다.


저작자표시

<링크>

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


<소스코드>

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<stdio.h>
#include<string.h>
int parent[1000001];
int find(int i)
{
    if (parent[i] == i)
        return i;
    int j = find(parent[i]);
    parent[i] = j;
    return j;
}
void combine(int i, int j)
{
    parent[find(j)] = find(i);
}
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
 
    for (int i = 0; i <= N; ++i)
        parent[i] = i;
    while (M--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a == 0)
            combine(b, c);
        else
            if (find(b) == find(c))
                printf("YES\n");
            else
                printf("NO\n");
    }
}
 
cs


<풀이>

union find로 풀었다.

처음엔 시간초과가 났었다.


1
2
3
4
5
6
7
8
int find(int i)
{
    if (parent[i] == i)
        return i;
    int j = find(parent[i]);
    parent[i] = j;
    return j;
}
cs

find할때 부모를 다 갱신해서 부모자식간 depth가 1이 되게끔 갱신해야하는데 처음엔 그걸 빼먹었었다.
예를들어 
union(2,3)
unoin(3,4)
unoin(1,2) 순으로 쿼리가 들어오면
4의 부모는 3
3의 부모는 2
2의 부모는 1이 된다.
이때 4의 최종부모를 찾을때(find)는 1까지 거슬러올라가는데 3만큼 시간이 걸리고
3의 최종부모를 찾을때는 2만큼의 시간이 걸리게 되므로 극단적인 그래프가 그려지면 시간이 오래걸린다.
따라서 4의 부모를 find할때 1까지 거슬러올라갔으면 다시 리턴해 내려오면서 2의부모, 3의부모, 4의부모를 다 1로 바꿔줘야한다.



저작자표시

+ Recent posts

티스토리툴바