09. 9차시 수업

01.cpp - union, enum

#include <stdio.h>

union a{

int a;

long long int b;

}; //a와b의 주소값이 같다. b에 값 입력하고 a만 따올수 있음

enum days{mon=7, tue, wed}; // 연달아서 들어감

int main(){

union a U;

U.b=999999999;

printf("%d\n", U.a);

enum days D;

printf("%d ",mon);

printf("%d\n", tue);

}

union은 주소값이 같은 원소들을 묶어놓을때 씁니다. 코드에서 볼 수 있듯, b에 값을 집어넣었지만 a도 같은 값을 가지고 있는 것을 볼 수 있습니다.

enum은 순차적인 값을 갖는 원소들을 묶어놓을때 씁니다. 

구조체에 대한 기본 설명은 http://sunrinnote.tistory.com/35 여기에 있습니다.

02.cpp - BFS 최단경로

http://sunrinnote.tistory.com/41 여기 BFS구현 있습니다.

이제 최단경로를 구해봅시다. 

#include <stdio.h>

#include <queue>

#include <memory.h>

using namespace std;

int arr[1001][1001];//인접행렬

int dist[1001]; //i까지의 최단경로

//용어정리 : 노드 = vertex(복수형 vertices), 간선 : edge

//인접행렬 : Adjacency matrix

//행렬곱셈 : i에서 j까지 두번만에 갈 수 있는 경우의 수

//BFS : 너비 우선 탐색

int main(){

memset(dist, -1, sizeof(dist));

int cnt=0;

queue<int> Q;

int n;

scanf("%d", &n);

int v;

scanf("%d", &v);

for(int i=0; i<v; ++i){

int a,b;

scanf("%d %d", &a, &b);

arr[a][b]=1;

arr[b][a]=1;

}

Q.push(1);

dist[1]=0;

while(!Q.empty()){

int p=Q.front();

for(int i=1; i<=n; ++i){

if(arr[p][i]){

if(dist[i]==-1){

dist[i]=dist[p]+1;

Q.push(i);

}

if(dist[i] > dist[p]+1){

dist[i]=dist[p]+1;

Q.push(i);

}

}

}

Q.pop();

}

printf("%d", dist[n]);

return 0;

}

std::queue에 대한 내용은 http://sunrinnote.tistory.com/70 여기에 있습니다.

memset(dist, -1, sizeof(dist)); 이거는 첫째 원소 배열에 두번째 원소를 세번째 원소만큼 채우는 겁니다.

BFS를 이용해서 구했습니다. 현재 있는 곳에서 원하는 곳으로의 경로가 원래 원하던 곳보다 적은 경로면 그 값으로 바꿉니다. 아 물론 처음 도달했을때는 무조건 그 값으로 채워줍니다.

코드 완성에 도움을 많이 준 상민이에게 감사의 말씀 전합니다~

03.cpp - 저울

/* https://www.acmicpc.net/problem/10159 */

#include <stdio.h>

#include <queue>

#include <memory.h>

using namespace std;

int arr[101][101];//인접행렬

int haspath[101][101];

int know[101];

int visit[101];

int N, M;

int main(){

queue<int> Q;

scanf("%d %d", &N, &M);

for(int i=1; i<=M; ++i){

int a,b;

scanf("%d %d", &a, &b);

arr[a][b]=1;//a보다 작은거들이 b.

}

for(int i=1; i<=N; ++i){

memset(visit, 0, sizeof(visit));

Q.push(i);

visit[i]=1;

while(!Q.empty()){

int f=Q.front();

Q.pop();

for(int j=1; j<=N; ++j){

if(visit[j]==1) continue;

if(arr[f][j]==1){

Q.push(j);

visit[j]=1;

haspath[i][j]=1;

haspath[j][i]=1;

}

}

}

int cnt=0;

}

for(int i=1;i<=N;i++)

{

int cnt = 0;

for(int j=1;j<=N;j++)

if(haspath[i][j]) cnt++;

printf("%d\n",N-cnt-1);

}

}

a번에서 b번으로 갈 수 있는 경로가 있는지 여부를 검사합니다. 

코드 완성에 도움을 많이 준 상민이에게 감사의 말씀 전합니다~