Grace

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

문제

ANT가 처음 알고리즘 대회를 개최하게 되면서 현수막을 내걸었다.

저번 학기 영상처리 수업을 듣고 배웠던 지식을 최대한 응용 해보고 싶은 혁진이는 이 현수막에서 글자가 몇 개인지 알아보는 프로그램을 만들려 한다.

혁진이는 우선 현수막에서 글자인 부분은 1, 글자가 아닌 부분은 0으로 바꾸는 필터를 적용하여 값을 만드는데 성공했다.

그런데 혁진이는 이 값을 바탕으로 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각만 하였다.

혁진이가 필터를 적용하여 만든 값이 입력으로 주어졌을 때, 혁진이의 생각대로 프로그램을 구현하면 글자의 개수가 몇 개인지 출력하여라.

입력

첫 번째 줄에는 현수막의 크기인 M와 N가 주어진다. (1 ≤ M, N ≤ 250)

두 번째 줄부터 M+1 번째 줄까지 현수막의 정보가 1과 0으로 주어지며, 1과 0을 제외한 입력은 주어지지 않는다.

출력

혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라.

접근방법 및 풀이

- 기본적인 BFS 알고리즘으로 해결했다.

- 대각선에 위치해도 인접한 것으로 보기때문에 탐색 시 상하좌우 외에 4가지 방향을 더 추가한다.

- 인풋배열의 0,0부터 bfs를 진행한다.

- 진행 중 방문한 곳의 인풋배열 값을 0 (글자)로 바꿔준다.

- bfs를 몇번 진행했는지가 곧 답이 된다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define VMAX 250+1
#define INF 987654321

using namespace std;

int n,m;
int b[VMAX][VMAX];
int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {1,0,-1,1,-1,1,0,-1};

void bfs(int sx, int sy){
  queue<pair<int,int>> q;
  int v[VMAX][VMAX]={0};
  q.push({sx,sy});
  v[sx][sy]=1;
  while(!q.empty()){
    int x = q.front().first;
    int 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 <m){
        if(v[nx][ny]==0 && b[nx][ny]==1){
          v[nx][ny]=1;
          b[nx][ny]=0;
          q.push({nx,ny});
        }
      }
    }
  }
}

int main()
{
  int result=0;
  cin >> n >> m;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin >> b[i][j];
    }
  }
  
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(b[i][j]==1){
        bfs(i,j);
        result++;
      }
    }
  }

  cout << result;

  return 0;
}

/*
8 19
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 0
0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

*/

느낀점

약간의 BFS 응용이 있어서 재밌고도 쉽게 풀렸다.

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

문제

N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.

각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다. 직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만큼이 들게 된다. 여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.

어느 날, 해커가 네트워크에 침입하였다. 네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다. 관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 슈퍼컴퓨터에만 설치할 수 있었다. 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고, 그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다. 준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다. 이때, 다음의 조건들이 만족되어야 한다.

1. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
2. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

원래의 네트워크에 대한 정보가 주어졌을 때, 위의 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.

출력

첫째 줄에 복구할 회선의 개수 K를 출력한다. 다음 K개의 줄에는 복구한 회선을 나타내는 두 정수 A, B를 출력한다. 이는 A번 컴퓨터와 B번 컴퓨터를 연결하던 회선을 복구한다는 의미이다. 출력은 임의의 순서대로 하며, 답이 여러 개 존재하는 경우에는 아무 것이나 하나만 출력하면 된다.

문제접근 및 풀이

1. 모든 노드가 연결되되,  최소개수의 회선만을 복구한다.
2. 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다

- 2번 조건이 의도하는 것이 무엇인지 명확히 와닿지 않아서 어려웠던 것 같다.

- 결국 2가지 조건을 만족하는 것을 슈퍼컴퓨터인 1번 노드 기준으로 dijkstra알고리즘을 돌리는 경우와 같다는 것을 떠올리는게 어려웠다.

- dijkstra 탐색 후 탐색 경로를 찾는 것은 parent 배열을 통하여 해결했다. priorit queue에 push 하는 과정에서 다음 노드의 parent 배열의 값을 현재 노드로 설정하면 재귀적으로 경로를 따라가는 것이 가능해 진다.

- 2번 배열값부터 마지막까지 parent 배열의 값과 i 값을 출력하면 이것이 곧 연결된 노드들을 의미한다. 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#define VMAX 1000 + 1
#define INF 987654321

using namespace std;

int n,m;
vector<pair<int,int>> a[VMAX];
int parent[VMAX];

void dijkstra(int start){
    int dist[VMAX];
    for(int i=0; i<VMAX; i++) dist[i] = INF;
    priority_queue<pair<int,int>> pq;
    pq.push({-0, start});
    dist[start]=0;
    //parent[start]=-1;
    while(!pq.empty()){
        int x = pq.top().second;
        int wx = -pq.top().first;
        pq.pop();
        for(int i=0; i<a[x].size(); i++){
            int y = a[x][i].first;
            int wy = a[x][i].second;
            if(dist[y] > wy + wx){
                dist[y] = wy + wx;
                pq.push({-dist[y], y});
                parent[y] = x;
            }
        }
    }
    return ;
}

int main()
{
    cin >> n >> m;
    for(int x,y,w,i=0; i<m; i++){
        scanf("%d %d %d", &x, &y, &w);
        a[x].push_back({y,w});
        a[y].push_back({x,w});
    }
    dijkstra(1);
    printf("%d\n", n-1);
    for(int i=2; i<=n; i++){
        printf("%d %d\n", parent[i], i);
    }
    return 0;
}

느낀점

- 주어진 조건을 보고 어떤 알고리즘으로 접근해야하는지 떠올리는 것이 쉽지 않았다. 약간의 힌트를 찾아보고 계속 대뇌이다 보니 그래도 이해가 되었다. 쉽지 않았다.

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

문제

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번,2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.

입력

첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.

둘째 줄에는 n개의 숫자가 차례대로  각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.

세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.

출력

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

문제접근 및 풀이

- 각 지역마다의 탐색에 대한 최대값을 구해야 한다.

- 각 지역에 대해 dijktras를 돌리면서 R 범위 이내에서 얻을 수 있는 최대 아이템 수를 구한다.

- R 범위 이내에 라는 범위를 고려해주는 것이 관건이였다.

- dijktras를 사용할 경우 어떤 지역에 대한 최소가중치가 한번에 정해지는 것이 아니라 동적으로 변화되기 때문에 동일한 지역을 2번 방문할 수 있다.

- 따라서 visit 배열을 통해 이미 방문했던 지역이라면 아이템수를 카운트하지 않고 처음방문인 경우에만 아이템을 카운팅하도록 한다.

인간은 합리적이지 않다. 자신도 모르는 사이에 온갖 환경과 각종 요소들에 의해 행동의 영향을 받는다. 저자는 넛지로서 본질적으로 합리적이지 못한 인간이 더 나은 삶을 영위할 수 있다고 주장한다.

인간과 이콘 : 우리는 천재인 동시에 바보다.

인간이 체계적으로 틀리는 방식

- 인간은 합리적이지 않다.

- 우리는 온갖 종류의 행동설계자에 의해 영향을 받으며 행동에 대한 무의식적인 편향을 지닌다.

- 사람들이 체계적으로 틀리느 방식을 통찰하여 인간해동에 대한 이해를 향상시킬 수 있다. 즉 넛지를 통해 더 나은 세상을 만든다!

자동시스템 vs 숙고시스템 (심리학에서의 시스템1과 시스템2)

- 우리는 본능적으로 자동시스템에 의지하게 되며 판단하고 행동하는 경향이 있다.

기준선 설정

- 사고 프로세스의 출발점을 미묘하게 제시받으면, 그 기준선에 의해 사고가 편향된다.

- 협상에서 가격을 처음부터 높게 제시할수록 더 많은 금액을 받을 수 있다.

입수가능성 발견법

- 관련 사례들이 얼마나 쉽게, 많이 떠오르는지에 따라 위험성을 판단하는 경향이 있다.

- 지진을 많이 겪었던 사람이 지진의 위험성을 그렇지 않는 사람보다 더 크다고 생각하는 경우이다.

비현실 낙관주의

- 대부분의 사람들은 자신이 평균이상이라고 생각한다.

현상유지 편향

- 현재의 상황을 되도록이면 그대로 유지하려는 성향이 있다.

프레이밍

- 어떤 수술의 결과로 100명 중 90명이 생존한다. vs 100명중 10이 죽는다 라는 선택지가 있다고 가정하자.

- 사람들은 생존에 관점에서 바라존 전자의 설명을 들었을때 수술에 대해 더 우호적으로 반응한다.

유혹에 저항하는 법

살을 빼고 싶다면 작은 그릇에 먹어라.

- 자동조종모드에서 최선 혹은 원하는 결과를 얻도록 조작하라.

계획하는 자아(원시적인)가 행동하는 자아(근시적인)의 행동을 통제하는 조취를 취하라.

- ex) 장보러 갈때 살 물품들 리스트를 꼭 작성하기. 알람맞추기 등

심적회계

- 예산을 용도별로 산정해 놓고 그에 따라 소비하라.

- 각 예산액을 대체할 수 없도록하면 과도한 소비욕구를 줄이는데 도움이 된다.

인간은 떼 지어 몰려다닌다

- 가장 효과적인 넛지 사용법은 사회적 영향을 활용하는 것이다.

1) 타인의 행동 혹은 사고

2) 통료집단의 압력

- 인간은 틀에 따르기를 좋아하기 때문에 타인에 의해 쉽게 넛지당한다.

집단동조 : 자신의 감각적 증거를 무시하는 이유

1) 사람들의 답변에서 모종의 정보가 전달되기 때문이다.

2) 사람들의 비난을 피하고 싶어하기 때문이다.

다원적무지

- 어떤 관행이나 전통을 따를때, 그 이유가 가치있어서가 아닌 대부분의 사람들이 좋아한다고 생각하기 때문이다.

조명효과

- 타인이 자신의 행동을 크게 주목한다고 생각하는 경향이 있다.

- 하지만 타인은 당신의 생각만큼 당신에게 큰 관심이 없다는 것이 진실이다.

사회적 넛지

- 금연률 상승 뉴스가 보도되면 이에 따라 금연률이 높아지는 결과를 유도할 수 있다.

구매의사 묻기

- 의향을 물음으로써 넛지를 가한다.

- 구매의사를 묻는 것 만으로도 구매률을 높일 수 있다.

- 단순 측정효과 : 의도에 대한 질문을 받았을때 자신의 답변과 행동을 일치시키는 현상이다.

넛지가 필요한 순간

- 어렵고 빈도가 낮으며 적절한 피드백이 없는 의사결정과 마주할 경우에 넛지가 필요하다.

- 선택안이 많고 복잡성이 높을수록 교화적인 선택설계가 필요하다. 간단해야 한다.

선택설계의 세계

자극 반응 일치성

- 신이 받는 신호(자극)가 바람직한 행동과 일치하기를 원한다.

디폴트

- 대부분의 사람들은 최소저항경로를 선택한다. 최소한의 노력을 요하는 옵션을 원한다.(유용성과 이득)

오류예상

- forcing function 기능강제

- 카드를 뽑아야지만 현금인출이 가능하도록 하는 것

피드백

- 피드백을 제공한다.

- 카메라의 '찰칵' 소리

복잡한 선택의 조직화

- 대안이 많을 수록 단순화 전략을 채택할 가능성이 높다.

넛지가 우리를 더 부유하게 한다.

저축,투자,대출 등의 어려운 과제들을 더 적절히 수행하는 방법

저축을 늘리는 방법 - 선택설계의 힘

- 은퇴연금가입을 늘리는 요린

1) 디폴트 옵션으로 설정하라 -> 자동가입 후 가입 해지하는 근로자가 거의 없다.

2) 능동적으로 결정하도록 요구한다.(단순화된 가입 절차) -> 경로요인

유용하고 관대한 투자 선택 설계

- 대부분의 사람들이 투자에 노련하지 못하다.

- 고점에서 매수하고 저점에서 매도한다.

- 인간은 손실을 싫어한다.

- 포트폴리오 점검 빈도가 높아질수록 리스크가 크다고 생각한다.

- 인간이 느끼기에 500의 손실의 정도와 1000이득의 정도가 맞먹는다.

- 디폴트, 오류예측, 피드백을 이용해 합리적인 투자를 하도록 유도하낟.

- ex. 목표액만기펀드, 자동가입독려, 가입자에 성향에 따라 투자설계에 관여하는 복잡도 조직화

신용시장

- 모기지, 학자금대출 등은 복잡하다. (티저금리, 변동금리, 각종 수수로, 포인트, 조기상환별과금 등등)

- 이에 따라 교육수준이 낮거나 고지식한 사람들의 불이익이 커진다. 

- 사람들이 교묘하게 이용당한다.

- 대안 :학자금 보조 신청서 간소화 / 상환일정공개 -> 인간보편적으로 지닌 약점을 보완하기 위해!

- 선택의 자유는 존중하되 몇가지 개선을 통해 치명적인 선택을 할 가능성을 낮춘다.

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

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.

출력

첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.

문제접근 및 풀이

- 최소스패닝 트리 알고리즘으로 해결할 수 있다.

- priority_queue을 이용하는 prim 알고리즘을 이용했다.

1. 아무 노드나 잡는다. -> 1번 마을로 하자. (어차피 모든 원소가 연결되어야 하므로 어디서 출발하든지 간에 상관없다.)
2. priority_queue가 빌때까지 진행
2.1 현재까지 탐색한 집합과 연결된 간선 중 가장 짧은 간선을 선택한다.

2.2 해당 간선의 목적지 노드 즉 y(x->y로 가는 간선의 가중치 w)와 연결된 모든 간선을 priority_queue에 넣는다.

두개의 마을 집합으로 나누는 방법
- 관리비용이 최소가 되도록 마을들을 2개의 집합으로 나눈다는 것은 곧 최소스패닝 트리를 구한 후 그 중에서 가장 큰 가중치는 갖는 간선을 제거한다는 의미와 같다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define VMAX 100000 + 1

using namespace std;

int n,m;
int v[VMAX]={0};
vector<pair<int,int>> a[VMAX];
int maxWeight=0;

int solve(){
    int result=0;
    priority_queue<pair<int,int>> pq; // w값과 y 값을 저장. -> 이 둘만 해도 가능하기 때문
    pq.push({-0, 1});
    // 굳이 1번 마을에 대한 주변 간선들을넣지 않아도 루프문에 의해 해결된다.
    while(!pq.empty()){
        int w = -pq.top().first;
        int x = pq.top().second;
        pq.pop();
        if(v[x]==1) continue;
        v[x]=1;
        
        result += w;
        maxWeight = max(maxWeight, w);
        for(int i=0; i<a[x].size(); i++){
            int y = a[x][i].first;
            int w = a[x][i].second; // 양방향 그래프인것을 고려하지 않음.
            pq.push({-w,y});
        }
    }
    return result;
}

int main()
{
    cin >> n >> m;
    for(int x,y,w,i=0; i<m; i++){
        scanf("%d %d %d", &x, &y, &w);
        a[x].push_back({y,w});
        a[y].push_back({x,w});
    }
    
    cout << solve() - maxWeight;
    
    return 0;
}

느낀점

- 알고리즘을 이해하는데 그치는게 아니라 꾸준히 문제푸는 등의 식으로 활용 및 체득하는 과정을 거치면서 점점 내것이 되어가는 것 같아 뿌듯하다.

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

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

문제접근 및 풀이

- 기본적인 BFS 알고리즘을 활용해서 해결하였다.

- 특별히 고려해야했던 것은 벽을 부수는 횟수 제한이 있다는 점이다.

- 입력받은 제한 횟수를 넘기지 않는 선에서 벽을 부수는 모든 경우를 탐색해야 한다.

- 따라서 방문체크를 할때 사용되는 배열을 3차원 배열로 설정하여 3개의 변수에 대해 (x좌표,y좌표,벽부순 횟수) 체크를 해줄 수 있도록 하였다.

#include <iostream>
#include <queue>
#include <cstring>
#define VMAX 1000

using namespace std;

int n,m,kmax;
int b[VMAX][VMAX];
int v[VMAX][VMAX][11]={0}; // 최대 10개 까지 부술수 있다. 0 ~ 10
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int bfs(){
    queue<pair<pair<int,int>,pair<int, int>>> q;
    q.push({{0,0},{0,1}});
    v[0][0][0]=1;
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int k = q.front().second.first;
        int c = q.front().second.second;
        //printf("x:%d, y:%d, k:%d, c:%d\n", x,y,k,c);
        q.pop();
        if(x==n-1 && y==m-1){
            return c;
        }
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >=0 && nx < n && ny >=0 && ny < m && v[nx][ny][k]==0){
                if(k < kmax && b[nx][ny]==1){
                    v[nx][ny][k+1]=1;
                    q.push({{nx,ny},{k+1, c+1}});
                }
                if(b[nx][ny]==0){
                    v[nx][ny][k]=1;
                    q.push({{nx,ny},{k,c+1}});
                }
            }
        }
    }
    return -1;
}

int main()
{
    cin >> n >> m >> kmax;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        for(int j=0; j<s.length(); j++){
            b[i][j] = s[j]-'0';
        }
    }
    cout << bfs();
    return 0;
}

느낀점

BFS의 기본적인 변형문제는 이제 손쉽게 풀 수 있는 수준이 된것 같아 뿌듯하다. 하지만 아직 많이 부족하니 더욱 더 노력해야겠다.

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

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

문제접근 및 풀이

union find 알고리즘을 연습할 수 있는 좋은 문제이다.

- 각 줄의 첫째 숫자가 0 이면 merge를 수행한다.

- 각 줄의 첫째 숫자가 1이면 같은 parent를 갖는지 확인 후 결과를 출력한다.

#include <iostream>
#define VMAX 1000000 + 1

using namespace std;

int parent[VMAX]={0};
int n;

int getparent(int x){
  if(parent[x]==x) return x;
  return parent[x] = getparent(parent[x]);
}

void merge(int sa, int sb){
  int a = getparent(sa);
  int b = getparent(sb);

  if(a==b) return ;
  if(a < b)
    parent[b]=a;
  else
    parent[a]=b;
}

bool sameparent(int sa, int sb){
  int a = getparent(sa);
  int b = getparent(sb);
  if(a==b) return true;
  else return false;
}


int main(){
  int m; cin >> n >> m;
  for(int i=0; i<=n; i++) parent[i]=i;

  for(int k,a,b,i=0; i<m; i++){
    scanf("%d %d %d", &k, &a, &b);
    if(k==0){
      merge(a,b);
    }else{
      bool p = sameparent(a,b);
      printf(p==true?"YES\n":"NO\n");
    }
  }
}

느낀점

몰랐던 알고리즘을 하나 하나 정복해 나가는 기분이 들어 뿌듯하다.

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

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

문제접근 및 풀이

- 최소 스패닝 트리 알고리즘의 개념을 연습할 수 있는 문제다.

- prim 알고리즘을 사용했다. (union find을 사용하는 크루스칼 알고리즘도 있다.)

프림 알고리즘

- 노드 중심으로 탐색한다. 
- priority_queue를 사용하여 가장 작는 가중치는 갖는 연결된 간선을 선택한다. 
- 이때 이미 방문한 노드면 pass한다 -> 방문한 노드만 아니면 싸이클이 무조건 안 생긴다.

- 방문하지 않은 노드에 한해서 해당 노드와 연결된 모든 간선을 priority_queue에 넣는다.
- pq가 빌때까지 진행한다. -> 이미 방문한 정점들이면 알아서 다 빠지기 때문이다.

#include <iostream>
#include <vector>
#include <queue>
#define VMAX 10001

using namespace std;

vector<pair<int,int>> a[VMAX];

int solve(){
  int result=0;;
  int v[VMAX]={0};
  priority_queue<pair<int,int>> pq; // priority_queue를 사용하여 연결된 간선중 가장 작은 가중치를 갖는 값을 우선적으로 탐색한다.
  pq.push({-0, 1}); // 어디서 시작하는지 관계없으므로 임의로 1번 정점에서 시작한다.
  //이때 1번 노드는 방문처리 하지 않는다. 1번 노드로 시작하는 것이지 탐색을 진행한게 아니기 때문이다.
  while(!pq.empty()){
    int x = pq.top().second;
    int w = -pq.top().first;
    pq.pop();
    if(v[x]==1) continue; // 이미 방문한 정점이면 pass

    result+=w; // 가중치 ++ 
    v[x]=1; // 방문체크
    for(int i=0; i<a[x].size(); i++){ // 방문한 노드에 연결된 모든 간선을 pq에 추가한다.
      int y = a[x][i].first;
      int wy = a[x][i].second;
      pq.push({-wy,y});
    }
  }

  return result;
}

int main(){
  int n,e; cin >> n >> e;
  for(int x,y,w,i=0; i<e; i++){
    scanf("%d %d %d", &x, &y ,&w);
    a[x].push_back({y,w});
    a[y].push_back({x,w});
  }
  cout << solve();
  return 0;
}

느낀점

- 최소스패닝 트리 알고리즘에 정답을 보지 않고 충분히 생각해 본 후에 프림알고리즘을 접하니 훨씬 이해가 쉬웠고 왜 알고리즘을 이렇게 짜여져야 하는지 쉽게 납득이 되고 채화시킬 수 있었다.