2178번 미로 찾기
bfs이므로 현재 방문할 수 있는 노드를 그냥 탐색하면서 탐색횟수를 저장해주면 된다.
탐색한 노드는 다시 방문하지 않아도 된다 (저장한 탐색 횟수가 1,1에서 현재 노드로 가는 최소 거리로 확정된다).
이후 탐색하는 과정에서 이미 탐색한 노드로 길이 이어질 수 있지만 그 경로는 다른 노드를 몇번 거쳐서 오는 것이므로(bfs이므로! ) 최소 거리가 아니고, 따라서 고려할 필요가 없다.
처음에는 최소 거리일 때, 저장한다라는 조건을 주어서 구현하였는데 굳이 이 조건은 필요가 없다. 탐색하면서 거리를 저장해주고, 방문을 기록해주고 반복하는 식으로 하면 된다.
#include<stdio.h>
#include<string>
#include<queue>
using namespace std;
int arr[105][105];
int minarr[105][105];
queue<pair<int, int>>q;
int tox[4] = { 0,0,-1,1 }; int toy[4] = { 1,-1,0,0 };
void bfs(int n,int m) { //탐색 & set min
q.push({ 1,1 });
pair<int, int> node; int x; int y;
int cycle = 0; int sum = 0; int prevsum = 1;
while (q.empty()==false) {
while (prevsum > 0) {
node = q.front(); x = node.first; y = node.second;
for (int i = 0; i < 4; i++) {
int nx = x + tox[i];
int ny = y + toy[i];
if (arr[nx][ny] == 1 && nx <= n && nx > 0 && ny > 0 && ny <= m) {
if (minarr[nx][ny] > cycle + 1) {
minarr[nx][ny] = cycle + 1; sum++;
q.push({ nx,ny });
}
}
}
q.pop(); prevsum--;
}
prevsum = sum; sum = 0;
cycle++;
}
printf("%d", minarr[n][m] + 1);
}
int main() {
// 1,1 to n,m
int n, m; scanf("%d%d", &n, &m);
int a;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%1d", &a);
arr[i][j] = a; minarr[i][j] = 10000000;
}
}
bfs(n, m);
}
1697번 숨바꼭질
dp인줄 알았다. dp로 풀다보니 예외처리해주어야 할 부분이 많았고 계속 틀렸습니다가 떴다.
결국 알아차리고 bfs로 풀어 보니 그리 어렵지 않았다. 하지만 만약 이 문제를 bfs로 풀어야 한다는 것을 알아차리지 못했다면...? 생각만해도 답답하다. 문제를 보고, 어떤 유형인지 파악하는 것이 중요한 것 같다.
dp와 그래프 탐색(bfs dfs)유형은 얼핏 보기에 비슷해 보일 수 있다.
배열에 정보를 메모이제이션한다는 점이 동일하기 때문이다. 그래서 여러 문제에서 초반에 헷갈렸다.
음 둘의 차이점을 생각해보니..
그래프 탐색
- 기본적으로 탐색★하는 문제인 경우
DP
- 이전의 경우로 이후의 경우를 계산할 수 있는 경우 (한방향으로 점화식이 수립될 수 있는 경우)
- 모든 경우를 다 고려해주어야 하는 경우 (그래프의 경우 갈 수 있는 경로만 따라가면 됨)
이때까지 풀어본 문제에서 생각한 것들이라서 앞으로 더 어려운 유형을 만나게 되면 수정이 필요할지도..
이 경우에는 i에서 i-1, i+1, i*2로 이동할 수 있다. dp로 풀게 되면 i-1에서 문제가 생긴다. 이전의 경우로 이후의 경우를 계산할 수 없다. 이전으로 다시 돌아가야 하는 경우도 생각해줘야 하기 때문에 이상한 사이클이 생길 수 있다.
따라서 i 노드가 i-1, i+1, i*2노드와 연결되어 있다고 생각하고, n노드에서 k노드로 가는 경로를 bfs로 찾아주어야 한다.
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int arr[200005];
int isvisit[200005];
queue<int> q;
void bfs(int n,int k) {
q.push(n);
int node; isvisit[n] = 1;
while (q.empty()==false) {
node = q.front();
if (node - 1 >= 0 && isvisit[node-1]==0) {
q.push(node - 1); isvisit[node - 1] = 1; arr[node-1] = arr[node] + 1;
}
if (node + 1 <= k * 2 && isvisit[node+1]==0) {
q.push(node + 1); isvisit[node + 1] = 1; arr[node+1] = arr[node] + 1;
}
if (node * 2 <= k * 2 && isvisit[node*2]==0) {
q.push(node * 2); isvisit[node * 2] = 1; arr[node*2] = arr[node] + 1;
}
q.pop();
if (isvisit[k] == 1) return;
}
}
int main() {
int n, k; scanf("%d%d", &n, &k);
bfs(n, k);
printf("%d", arr[k]);
}
7 10
1
1 2 3
1 3 1
2 3 2
2 5 5
3 5 6
3 6 1
3 4 2
4 6 8
5 6 7
6 7 1
18870번 좌표 압축
#include<stdio.h>
#include<map>
using namespace std;
multimap<int, int> m;
multimap<int, int>::iterator iter;
int arr[1000005];
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
m.insert({ arr[i],i });
}
iter = m.begin();
int index = 0; int prev;
arr[(*iter).second] = index;
prev = (*iter).first;
while (iter != m.end()) {
if ((*iter).first != prev) {
index++;
}
arr[(*iter).second] = index;
prev = (*iter).first;
iter++;
}
for (int i = 1; i <= n; i++) printf("%d ", arr[i]);
}
'코딩) PS 공부 [백준]' 카테고리의 다른 글
PS) 백준 퇴사 (0) | 2021.06.24 |
---|---|
PS) 1012, 2583, 2468, 2644번 (유기농 배추, 영역 구하기, 안전 영역, 촌수 계산) (0) | 2021.05.13 |
PS) 백준 7569, 11724, 7562, 2667, 2606번 (토마토, 연결 요소의 개수, 나이트의 이동, 단지번호 붙이기, 바이러스) (0) | 2021.05.12 |
PS) 백준 12764, 7576, 1260번 (싸지방에 간 준하, 토마토, DFS와 BFS) in c++ (0) | 2021.05.11 |
PS) 백준 1720번 (타일 코드) 너ㅓㅓㅓㅓㅓㅓㅓ무 하기 싫고 안풀리는날인데 짜증나아 (0) | 2021.05.06 |
댓글