본문 바로가기

Problem Solving

 (135)
[ BOJ 백준 11403번 - 경로 찾기 ] 해설 및 코드 https://www.acmicpc.net/problem/11403 목적 모든 두 정점간의 경로가 존재하는지 구하자. 접근법 1. 플로이드 와샬 알고리즘으로 접근하자. 2. 알고리즘에 의해 i에서 j로 k를 거쳐갈 때, i와 k간의 경로가 존재하고 k와 j간의 경로가 존재하면 i와 j간의 경로가 존재하는 것이므로 값을 갱신한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include #define f(i,l,r) for(int i=l;i>n;f(i,0,n)f(j,0,n)cin>>a[i][j]; f(k,0,n)f(i,0,n)f(j,0,n)if(a[i][k]&&a[k][j])a[i][j]=1; f(i,0,n){ f(j,0,n)cout
[ BOJ 백준 1719번 - 택배 ] 해설 및 코드 https://www.acmicpc.net/problem/1719 목적 모든 정점쌍 간의 최단거리를 구하고, 거쳐가야 할 정점을 구하자. 접근법 1. 문제 분류는 다익스트라이지만, 모든 두 정점간의 최단 거리를 구해야하므로, 플로이드 와샬 알고리즘이 더 적합하다고 본다. 2. 플로이드 와샬 알고리즘에 의해 K 정점에 따라 최단 거리가 갱신될 때, 거쳐가야하는 첫번째 노드를 갱신해준다. 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 #include #define f(i,l,r) for(int i=l;i>n>>m; f(i,1,n)f(j,1,n)g[i][j]=INF; f(i,1,n)g[i][i]=..
[ BOJ 백준 1261번 - 알고스팟 ] 해설 및 코드 https://www.acmicpc.net/problem/1261 목적 (1,1)에서 (N,M)으로 가기 위해 거쳐가야 하는 1의 개수의 최소값을 구하자. 접근법 1. bfs 알고리즘을 이용하여 최소값을 갱신해 나가자. 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 #include #define f(i,l,r) for(int i=l;ival){ b[x][y]=val; q.push({x,y}); } } } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>m>>n; f(i,0,n)cin>>a[i]; ..
[ BOJ 백준 6118번 - 숨바꼭질 ] 해설 및 코드 https://www.acmicpc.net/problem/6118 목적 다음 그림과 같은 그래프에서 1번 정점과 다른 정점들과의 최단 거리를 구한 뒤, 그 중에서 가장 긴 길이의 정점에 관한 정보를 구하자. 접근법 1. bfs알고리즘을 이용하여 이전에 갱신한 거리보다 작은 경우 거리를 갱신하며, 이를 더이상 갱신할 것이 없을 때까지 반복한다. ( 백준 8061 - Bitmap문제와 유사한 방식을 이용한다.) 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 #include #include #include #include #define f(i,l,r) for(int..
[ BOJ 백준 8061번 - Bitmap ] 해설 및 코드 https://www.acmicpc.net/problem/8061 목적 임의의 (i, j)에서 1이 있는 좌표(white pixel)와의 최단 거리를 구하자. 접근법 1. white pixel들의 좌표를 모두 queue에 담아 bfs 알고리즘을 이용하여 거리를 갱신해준다. 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 #include #include #define f(i,l,r) for(int i=l;i= ans[ni][nj]) continue; ans[ni][nj] = nk; q.push({ ni,nj,nk }); } } } int main(..
[ BOJ 백준 2606번 - 바이러스 ] 해설 및 코드 https://www.acmicpc.net/problem/2606 목적 1번 컴퓨터와 연결된 컴퓨터의 개수를 구하자. 접근법 1. 아주 많은 접근법이 있지만, Disjoint-set 자료구조를 이용하여 접근했다. 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 #define f(i,l,r) for(int i=l;in; f(i,1,n)p[i]=i,size[i]=1; int m;cin>>m; while(m--){ int a,b;cin>>a>>b; combine(a,b); } cout
[ BOJ 백준 3430번 - 용이 산다 ] 해설 및 코드 https://www.acmicpc.net/problem/3430 목적 비가 내려 호수에 물이 넘치지 않도록 용이 호수 물을 먹는 순서를 구하자. 접근법 1. t[i]가 자연수일때, 즉 비가 내릴 때, 미리 우물을 비워야 한다. 탐욕적으로 비가 내리지 않는 날 중에서 가능한 가장 이른 날을 선택해야 한다. 왜냐하면 매 순간마다 선택할 수 있는 선택지를 최대한 많이 확보해야 하기 때문이다. 2. 선택할 수 있는 범위는, t[j]==t[i](j는 jt; if(t==0){ s.insert(i); ans[i]=0; } else{ set::iterator it=s.upper_bound(a[t]); if(it==s.end()){ while(m-->i)cin>>t; return false; } ans[*it]=t; ..
[ BOJ 백준 1840번 - 스도쿠 ] 해설 및 코드 https://www.acmicpc.net/problem/1840 목적 스도쿠에 채워 넣을 번호가 81개의 줄에 걸쳐서 주어진다. 이때, 실수한 단계가 몇 번째인지 구하자. 접근법 1. 1~81번까지 올바른 입력인지 확인하기에는 시간제한에 걸린다. 이분탐색으로 확인할 단계 수를 줄이든, 틀린 위치부터 단계를 거슬러 올라가면서 구해야한다. 이분탐색은 72ms 정도가 걸린다. 후자의 방법은 0ms. 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 #define f(i,l,r) for(int i=l;i>..

티스토리툴바