기타:: 230117 일기

백준 풀이 - BFS 연습문제

문제리뷰

1012 유기농 배추: 테스트 케이스가 하나의 입력에 여러 개이기 때문에 초기화를 map과 vis 둘 다 해줘야 함.

7569 토마토 : Tuple 사용방법 익히기

// tuple 생성1
tuple<int, int, int> t = make_tuple(1, 2, 3)l

// tuple 생성2 - C++11
tuple<int, int, int> t = {1, 2, 3}

// tuple 값 가져오기
int i = get<0>(t);
int j = get<1>(t);
int k = get<2>(t);

5427 불 : BFS 두번 돌리는거 헷갈려.. 상근이의 이동 시간이랑 불 시간 비교할 때 변수 잘못 써서 헤맴.

>> (dist2[cur.X][cur.Y] + 1 >= dist1[nx][ny] 랑 비교해야하는데 dist2[nx][ny]랑 비교함)

1012 유기농 배추

#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 ground[50][50];
int vis[50][50];

int t, m, n, k;
int x, y;

// 시작점이 여러개인 BFS 유형
int BFS() {
	queue<pair<int, int>> Q;
	
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(vis[i][j] || ground[i][j] != 1) continue;
			vis[i][j] = 1;
			Q.push({i, j});
			cnt++;
			
			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] || ground[nx][ny] != 1) continue;
					vis[nx][ny] = 1;
					Q.push({nx, ny});
				}
			}
		}
	}
	
	return cnt;
}

int main() {
	cin >> t;
	
	for(int i = 0; i < t; i++) {
		cin >> m >> n >> k;
        
        // 초기화!
		for(int j = 0; j < n; j++) {
			fill(ground[j], ground[j]+m, 0);
			fill(vis[j], vis[j]+m, 0);
		}
		for(int j = 0; j < k; j++) {
			cin >> x >> y;
			ground[y][x] = 1;
		}

		cout << BFS() << '\n';
	}
}

 

5427 불

#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;
int w, h;
string building[1000];
int dist1[1000][1000];	// 불 시간
int dist2[1000][1000];	// 상근 이동 시간

void BFS() {
	queue<pair<int, int>> Q1;	// 불
	queue<pair<int, int>> Q2;	// 상근
	
	for(int i = 0; i < h; i++) {
		fill(dist1[i], dist1[i]+w, -1);
		fill(dist2[i], dist2[i]+w, -1);
	}
	
	// 불
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			if(building[i][j] == '*') {
				dist1[i][j] = 0;
				Q1.push({i, j});
			}
			if(building[i][j] == '@') {
				dist2[i][j] = 0;
				Q2.push({i, j});
			}
		}
	}
	
	while(!Q1.empty()) {
		pair<int, int> cur = Q1.front(); Q1.pop();
		for(int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			
			if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
			if(dist1[nx][ny] >= 0 || building[nx][ny] == '#') continue;
			
			dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
			Q1.push({nx, ny});
		}
	}
	
	while(!Q2.empty()) {
		pair<int, int> cur = Q2.front(); Q2.pop();
		for(int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			
            // 여기 조건부터 막혔음
			if(nx < 0 || nx >= h || ny < 0 || ny >= w) {
				cout << dist2[cur.X][cur.Y] + 1 << '\n';
				return;
			}
			if(dist2[nx][ny] >= 0 || building[nx][ny] == '#') continue;
			// 이 조건 때문에 계속 헤맴..
            if(dist1[nx][ny] >= 0 && dist2[cur.X][cur.Y]+1 >= dist1[nx][ny]) continue;
			
			 
			dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
			Q2.push({nx, ny});
		}
	}
	cout << "IMPOSSIBLE" << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> w >> h;
		for(int j = 0; j < h; j++) {
			cin >> building[j];
		}
		
		BFS();
	}
}