기타:: 230116 일기

백준 풀이 - BFS 예제

문제리뷰

2178 미로 탐색 : 초기화 - fill함수 / dist를 -1로 초기화해서 vis 변수를 없앨 수 있음

7576 토마토 : 모든 익지 않은 토마토들에 대해 가장 가깝게 위치한 익은 토마토까지의 거리를 구해야한다는 관점

>> (최단 거리 구하는거랑 연결지을 수 있어야 함)

4179 불! : if(dist2[nx][ny] >= 0 || miro[nx][ny] == '#') continue;

>> (조건 빼먹어서 메모리 초과 계속 발생함), 지훈이 이동 시간을 새로운 변수로 둬서 계산하는 방법 기억하기

1697 숨바꼭질 : 범위를 내맘대로 0 ~ 100,000로 잡았는데 넘어갈 수 있다! 단, *2를 하면 -1로 이동해야하므로 200,000까지 범위로 잡는게 적절하다.

 

 

2178 미로 탐색

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int n, m;
int board[100][100];
int vis[100][100];
int dis[100][100];	// -1로 초기화 하면 vis 없앨 수 있음
queue<pair<int, int>> Q;

int main() {
	cin >> n >> m;
	
	string tmp;
	for(int i = 0; i < n; i++) {
		cin >> tmp;
		for(int j = 0; j < m; j++) {
			board[i][j] = tmp[j] - '0';
		}
	}
	
	vis[0][0] = 1;
	dis[0][0] = 1;
	Q.push({0, 0});
	
	while(!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();
		
		for(int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			
			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if(vis[nx][ny] || board[nx][ny] != 1) continue;
			
			vis[nx][ny] = 1;
			dis[nx][ny] = dis[cur.X][cur.Y] + 1;
			
			Q.push({nx, ny});
		}
	}
	
	cout << dis[n-1][m-1];
}

 

7576 토마토

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int n, m;
int tomato[1000][1000];
int vis[1000][1000];
queue<pair<int, int>> Q;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> m >> n;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> tomato[i][j];
		}
	}
	
	int days = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(tomato[i][j] == 1)
				Q.push({i, j});
		}
	}
	
	while(!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();
		if(days < tomato[cur.X][cur.Y]) days = tomato[cur.X][cur.Y];

		for(int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			
			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if(tomato[nx][ny] != 0) continue;
			
			tomato[nx][ny] = tomato[cur.X][cur.Y] + 1;
			Q.push({nx, ny});
			
			if(days < tomato[nx][ny]) days = tomato[nx][ny];
		}
	}
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(tomato[i][j] == 0) {
				cout << -1;
				return 0;	
			}
		}
	}
	
	cout << days-1;
}

 

4179 불!

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int r, c;
string miro[1000];
int dist[1000][1000];
int dist2[1000][1000]; // 지훈이 이동 시간

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> r >> c;
	for(int i = 0; i < r; i++) {
		fill(dist[i], dist[i]+c, -1);
		fill(dist2[i], dist2[i]+c, -1);
	}
	
	queue<pair<int, int>> Q;
	char temp;
	pair<int, int> jihun;
	for(int i = 0; i < r; i++) {
		cin >> miro[i];
		for(int j = 0; j < c; j++) {
			temp = miro[i][j];
			if(temp == 'F') {
				dist[i][j] = 0;
				Q.push({i, j});
			}
			if(temp == 'J'){
				jihun = {i, j};
				dist2[i][j] = 0;
			}
				
		}
	}
	
	while(!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();
		
		for(int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			
			if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			if(dist[nx][ny] >= 0 || miro[nx][ny] == '#') continue;
			
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
			Q.push({nx, ny});
		}
	}

	Q.push(jihun);
	
	int t = 1;
	while(!Q.empty()) {
		pair<int, int> cur = Q.front();
		t = dist2[cur.X][cur.Y];
		Q.pop();
		
		for(int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			
			if(nx < 0 || nx >= r || ny < 0 || ny >= c) {
				cout << t+1;
				return 0;
			}
            
            // 조건 주의해서 다시 생각하기
			if(dist2[nx][ny] >= 0 || miro[nx][ny] == '#') continue;
			if(dist[nx][ny] >= 0 && dist[nx][ny] <= t+1) continue;
			
			dist2[nx][ny] = t+1;
			Q.push({nx, ny});
		}
	}
	
	cout << "IMPOSSIBLE";
}

 

1697 숨바꼭질

#include <bits/stdc++.h>
using namespace std;

int n, k;
int dot[100001];
int dx[] = {-1, 1, 2};
queue<int> Q;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	fill(dot, dot+100001, -1);
	cin >> n >> k;
	Q.push(n);
	
	while(!Q.empty()) {
		int cur = Q.front();
		Q.pop();
		if(cur == k) {
			cout << dot[k]+1;
			return 0;
		}
		
		for(int dir = 0; dir < 3 ; dir++) {
			int nx;
			if(dx[dir] == 2) nx = cur * dx[dir];
			else nx = cur + dx[dir];
			
            // 범위에 대한 생각 한번 더 해보기
			if(nx < 0 || nx >= 100001) continue;
			if(dot[nx] >= 0) continue;
			
			dot[nx] = dot[cur] + 1;
			Q.push(nx);
		}
	}
	
	cout << dot[k]+1;
}