동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.
도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.
입력
첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.
출력
첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.
문제접근 및 풀이
- 처음에 직관적으로 든 생각은 여행계획을 차례차례 따라가면서 bfs를 진행하여 각각의 경로에 대해 가능한 경로가 있는지 확인하는 방법이었다. 당연히 비효율적이고 시간초과가 날것을 알았기에 더 생각해보았다.
- 주어진 인풋배열에 대해 이 칸들을 dp처럼 채워나가면서 모든 정보를 활용해서 온전한 배열(어떻게든 연결되어있다면 1)을 만들 수 있을 것 같다고 생각했다.
- 따라서 플로이드 와샬 알고리즘을 이용해서 해결했다.
- i에서 j로 가는 경로가 0 일때 i에서 k로 가는 것과 k에서 j로 가는 경우가 존재한다면 b[i][j]가 참이 되도록하는 점화식을 가진다.
참고
- 여행루트가 1 1 이런식으로 자기자신일때, 해당 값을 참으로 설정해놓지 않으면 반례에 걸리게 되었다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define VMAX 200
#define INF 987654321
using namespace std;
int main(){
int n, m; cin >> n >> m;
int b[VMAX][VMAX]={0};
int s[1000]={0};
bool pass = true;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
scanf("%d", &b[i][j]);
if(i==j) b[i][j]=1; // 반례 => 초기화해주어야 했음
}
}
for(int i=0; i<m; i++)
scanf("%d", &s[i]);
for(int k=0; k<n; k++){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(b[i][j]==0 && b[i][k]==1 && b[k][j]==1){
b[i][j]=1;
}
}
}
}
for(int i=0; i<m-1; i++){
int x = s[i]-1;
int y = s[i+1]-1;
if(b[x][y]==0){
pass=false;
}
}
if(pass){
printf("YES\n");
}else{
printf("NO\n");
}
return 0;
}
느낀점
- 생각 끝에 예전에 알게되었던 플로이드 와샬을 떠올리고 이걸 적용하면 될것같은데? 하고 해결하게 되어 뿌듯하다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
문제풀이 및 접근
- dijkstra 알고리즘을 이용하였다.
- 각 학생별로 N번 마을에 대해 왔다 갔다하는 경로를 구해야 한다.
1. n번마을에서 모든 학생에게로 가는 최단거리 배열 tdist 값을 구한다.
2. 각 학생별 n 번 마을에 대한 최단경로를 구하면서 구한 값(학생->n 최단거리) + tdist의 배열값(n->학생 최단거리) 중 최대값을 구한다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define VMAX 1001
#define INF 987654321
using namespace std;
int n,e,target;
vector<pair<int,int>> a[VMAX];
int dist[VMAX];
int dijkstra(int start){
priority_queue<pair<int,int>> pq;
for(int i=0; i<VMAX; i++) dist[i]=INF;
pq.push({-0, start});
dist[start]=0;
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] > dist[x] + wy){
dist[y] = dist[x] + wy;
pq.push({-dist[y], y});
}
}
}
return -1;
}
int main(){
cin >> n >> e >> target;
int tdist[VMAX];
int result=0;
for(int x,y,w,i=0; i<e; i++){
scanf("%d %d %d", &x, &y, &w);
a[x].push_back({y,w});
}
dijkstra(target);
for(int i=1; i<=n; i++){
tdist[i] = dist[i];
}
for(int i=1; i<=n; i++){
if(i==target) continue;
dijkstra(i);
result = max(result, tdist[i] + dist[target]);
}
cout << result;
}
느낀점
처음에는 tdist배열을 따로 두어 비교할 생각을 못해서 dijktras 함수를 따로 하나 더 만들어서 접근했다. 코딩하면서 뭔가 비효율적이라는 생각이 들어서 좀 더 고민을 하다가 tdist배열을 통해 깔끔하게 해결한것 같아 기분이 좋다.
도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)
그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.
입력
첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.
둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.
셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.
출력
모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.
문제접근 및 풀이
- 문제를 해결한 후에 찾아보니 최소스패닝트리라는 개념의 문제라고 한다.
1.각 노드마다 최소가중치를 찾기위해 priority_queue를 이용한다.
2. 최소가중치를 갖는 노드를 하나 찾는다. -> vector에 추가
3. 이 노드를 시작으로 그래프를 넓혀나가기 시작한다.
3.1 vector에 추가된 각 노드에 해당하는 큐의 top값 중 최소값을 갖는 간선을 선택한다.
3.2 만일 이 간선이 이미 저장된 노드들을 연결하는 것이라면 필요없으므로 pop한다.
3.3 새로운 노드와 연결되는 간선이라면 새로운 노드를 벡터에 추가하고 result에 해당 가중치를 더한다.
3.4 벡터의 크기가 주어진 노드의 수가 될때까지 반복한다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define VMAX 1001
#define INF 987654321
using namespace std;
vector<int> findN;
priority_queue<pair<int,int>> pq[VMAX];
int n,e;
int result=0;
int solve(int x){
findN.push_back(x);
while(1){
if(findN.size() == n) break;
int minW=INF, minX, minY;
for(int i=0; i<findN.size(); i++){
int cur = findN[i];
if(!pq[cur].empty()){
// 지금까지 만들어진 그래프의 중 한 노드에 대해 - 노드 값이 존재하면
int w = -pq[cur].top().first;
int y = pq[cur].top().second;
if(minW > w){
minW = w;
minX = cur;
minY = y;
}
}
}
if(find(findN.begin(), findN.end(), minY) == findN.end()){
// 없음 -> 즉 통과, 추가해야함
findN.push_back(minY);
result+=minW;
}else{
pq[minX].pop();
}
}
return result;
}
int main(){
cin >> n >> e;
int minW=INF, minX, x;
for(int y,w,i=0; i<e; i++){
scanf("%d %d %d", &x, &y, &w);
pq[x].push({-w, y});
pq[y].push({-w, x});
if(minW > w){
minW = w;
minX = x;
}
}
cout << solve(minX);
return 0;
}
느낀점
1. (거의)혼자의 힘으로 최소스패닝트리라는 개념을 떠올려내고 고비가 있었지만 구현을 성공시켜서 뿌듯하다!
2. 고비,,, -> solve함수로 넘기는 변수를 x라고 해놓고 함수안에서 최소 가중치를 갖는 노드의 출발지를 갱신할때 cur가 아니라x라고 해놓은것 때문에 버그를 거의 1시간 내내 찾았다. 다음부터는 변수명을 좀더 명확하게 해야겠다 ㅠㅠ
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다.
x
x
x
x
말
x
x
x
x
근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.
이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야한다. 인접한 네 방향으로 한 번 움직이는 것, 말의 움직임으로 한 번 움직이는 것, 모두 한 번의 동작으로 친다. 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.
출력
첫째 줄에 원숭이의 동작수의 최솟값을 출력한다. 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.
문제접근 및 풀이
- 일반적인 bfs로 접근하여 쉽게 풀수 있는 문제이다.
- 다만 말이동이라는 추가적인 조건이 붙어있기에 이를 고려해주어야 한다.
- 같은 좌표에 도달하더라도 k 값 즉 말 이동 횟수에 따라 다른 상태를 나타내므로 말 이동 횟수에 따라 방문체크를 달리해줘야 한다. 말이동을 해서 특정칸에 온 경우와 말이동을 쓰지 않고 온경우는 다르게 봐야하기 때문이다.
- 따라서 3차원 방문배열을 사용해야 한다. (x, y, k)
#include <iostream>
#include <algorithm>
#include <queue>
#define VMAX 200
#define KMAX 31
using namespace std;
int k,w,h;
int b[VMAX][VMAX];
bool v[VMAX][VMAX][KMAX]={0};
int dx[12]={0, 0, 1, -1, -1, -2, -2, -1, 1, 2, 2, 1};
int dy[12]={1, -1, 0, 0, -2, -1, 1, 2, 2, 1, -1, -2}; // 0~3은 인접이동, 4~11은 말이동
void bfs(int sk){
queue<pair<pair<int,int>,pair<int,int>>> q; // x,y, depth, k
q.push({{0,0},{0,0}});
v[0][0][0]=true;
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
int depth = q.front().second.first;
int k = q.front().second.second;
q.pop();
if(x==h-1 && y==w-1){
printf("%d", depth);
return ;
}
for(int i=0; i<4; i++){
int X = x + dx[i];
int Y = y + dy[i];
if(X>=0 && Y>=0 && X<h && Y<w && v[X][Y][k]==false && b[X][Y]==0){
v[X][Y][k]=true;
q.push({{X,Y},{depth+1,k}});
}
}
if(sk > k){
for(int i=4; i<12; i++){
int X = x + dx[i];
int Y = y + dy[i];
if(X>=0 && Y>=0 && X<h && Y<w && v[X][Y][k+1]==0 && b[X][Y]==0){
v[X][Y][k+1]=1;
q.push({{X,Y},{depth+1,k+1}});
}
}
}
}
printf("-1");
}
int main(){
cin >> k;
cin >> w >> h;
for(int i=0; i<h; i++){
for(int j=0; j<w; j++){
scanf("%d", &b[i][j]);
}
}
bfs(k);
return 0;
}
느낀점
문제풀이 중간에 정답이 아닐 이유가 도저히없는데,, 왜 안되는거지?? 라는 생각을 가졌다. 한 50여분 고민끝에 답이 나오지 않자 나와 비슷하게 접근한 다른 사람의 코드는 한줄한줄 비교해 나갔다. 거의 다 비교가 끝나갈 무렵에도 내가 맞았다는 확신에 차있었다. 하지만 결국 내가 실수했다는 것을 깨닫게 되었다.
말이동을 할 경우 방문체크를 할때 k를 1 늘린 방문배열에 대해 확인을 해줘야 하는데 현재 k 값에 대해 방문체크를 하고 있었다...
-> 앞으로 생각한 후 코드를 짰는데도 오류가 있다면 반례 혹은 오류를 발견할때 까지 1시간정도의 시간을 소요해서 생각을 하는 시간을 갖자.
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.
준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.
준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.
입력
첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)
둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.
출력
첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.
접근방법 및 풀이
- 점화식을 구해 dp로 풀 수 있다.
- i,j번째 값은 i-1,j / i,j-1 / i-1,j-1번째 dp배열값중 최대값 + i,j번째 칸의 사탕개수 이다.
지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.
2
4
5
3
3
2
5
2
7
6
2
4
그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보
빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.
그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.
2
4
1
1
1
5
5
4
1
2
그림 2
3
4
3
2
그림 3
한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
입력
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
출력
첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.
문제접근 및 풀이
- 1년이 지날때 마다 bfs를 통해 이분화되었는지를 확인한다.
- 각 년도 마다 모든 바닷물 칸에 대해 인접한 빙산들의 높이를 한칸씩 줄인다.
- 모든 칸에 대해 탐색하면서 빙산이 있고 아직 탐색하지 않은 자리가 발견되면 bfs를 진행한다.
- bfs가 2번이상 진행된 경우 분열된것이므로 해당 년수 출력
- bfs가 0번 진행된 경우 이분화되지 않은 채 모든 빙산이 녹아 없어진 것이므로 0출력
#include <iostream>
#include <algorithm>
#include <queue>
#define VMAX 301
using namespace std;
int n,m;
int b[VMAX][VMAX];
bool c[VMAX][VMAX];
int v[VMAX][VMAX]={0};
int result=0;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int countb=0;
int years=0;
void bfs(int sx, int sy, int v[][VMAX]){
queue<pair<int,int>> q;
q.push({sx,sy});
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
//printf("x:%d y:%d\n",x,y);
for(int i=0; i<4; i++){
int X = x+dx[i];
int Y = y+dy[i];
if(b[X][Y]!=0 && v[X][Y]==0){ // 빙산이 있고 방문안했으면
v[X][Y]=1;
q.push({X,Y});
}
}
}
}
int main(){
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
scanf("%d", &b[i][j]);
}
}
while(1){
for(int i=0; i<=n; i++){ // 빙산체크초기화
for(int j=0; j<m; j++){
if(b[i][j]==0) c[i][j]=false; // 빙산이 있으면 true
else c[i][j] = true;
}
}
countb=0;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
v[i][j]=0;
for(int i=1; i<n-1; i++){ // BFS로 이분되었는지 탐색
for(int j=1; j<m-1; j++){
if(b[i][j]!=0 && v[i][j]==0){
bfs(i,j, v);
countb++;
}
}
}
if(countb>=2) break;
if(countb==0){ // 모든 빙산이 없어졌으므로 끝까지 분리되지 못한것이다.
printf("0");
return 0;
}
years++;
for(int i=1; i<n-1; i++){ // 1년 후 시간진행
for(int j=1; j<m-1; j++){
for(int k=0; k<4; k++){
int X = i+dx[k];
int Y = j+dy[k];
if(c[X][Y]==false && b[i][j] > 0){
b[i][j]--;
}
}
}
}
}
printf("%d", years);
}
