2178 미로 탐색

문제 링크
BFS 문제이다. y,x를 기반으로 해서 2차원 배열을 사용했다.

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

const int max_n = 104;
int dy[4]={-1, 0, 1, 0};
int dx[4]={0, 1, 0, -1};
int n,m,a[max_n][max_n],visited[max_n][max_n],y,x;

int main()
{
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            scanf("%1d", &a[i][j]);
        }
    }
    queue<pair<int,int>> q;
    visited[0][0]=1;
    q.push({0,0});
    
    while(q.size())
    {
        tie(y,x)=q.front(); q.pop();
        for(int i=0; i<4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny<0 || ny>=n || nx<0 || nx>=m || a[ny][nx]==0) continue;
            if(visited[ny][nx]) continue;
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }
    
    printf("%d", visited[n-1][m-1]);
    return 0;
}

---

1012 유기농 배추

문제 링크
connected component 개수를 찾는 문제이다.
DFS, BFS 모두 구현 가능한데 DFS가 조금 더 코드 길이도 짧다

#include<iostream>
using namespace std;

int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int m,n,k,y,x,ret,ny,nx,t;
int a[51][51];
bool visited[51][51];

void dfs(int y, int x)
{
    visited[y][x]=1; // 방문 처리
    for(int i=0; i<4; i++)
    {
        ny = y + dy[i];
        nx = x + dx[i];
        if(ny<0 || nx<0 || ny>=n || nx>=m) continue;
        if(a[ny][nx] == 1 && !visited[ny][nx])
        {
            dfs(ny, nx);
        }
    }
    return;
}

int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    while(t--)
    {
    	// 다음 테스트 케이스를 위해 초기화해준다
        fill(&a[0][0], &a[0][0] + 51*51, 0);
        fill(&visited[0][0], &visited[0][0] + 51*51, 0);
        ret = 0;
        
        cin >> m >> n >> k;
        for(int i=0; i<k; i++)
        {
            cin >> x >> y;
            a[y][x]=1;
        }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(a[i][j]==1 && !visited[i][j])
                {
                    dfs(i,j);
                    ret++; // 하나의 component에 대한 dfs가 끝나면 ret++
                }
            }
        }
        cout << ret << '\n';
    }
    return 0;
}

---

14502 연구소

문제 링크
순서 상관없이 3개의 벽을 세운다 : combination

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

int a[10][10], visited[10][10], n, m, ret;
vector<pair<int, int>> virusList, wallList; // 좌표값 기반
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};

void dfs(int y, int x){
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx] || a[ny][nx] == 1) continue;
        visited[ny][nx] = 1;
        dfs(ny, nx);
    }
    return;
}

// 벽을 세우는 여러 경우의 수마다 바이러스를 퍼뜨리는데 매 경우마다 초기화해줘야 한다
int solve(){
    fill(&visited[0][0], &visited[0][0] + 10 * 10, 0); // 초기화
    for(pair<int, int> b : virusList){
        visited[b.first][b.second] = 1;
        dfs(b.first, b.second);
    } 

    int cnt = 0; // 안전영역 카운트
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 0 && !visited[i][j]) cnt++; 
        }
    } 
    return cnt;  
}

int main(){
    cin >> n >> m;
    for(int i = 0; i <n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
            if(a[i][j] == 2) virusList.push_back({i, j});
            if(a[i][j] == 0) wallList.push_back({i, j});
        }
    }
    // wallList.size() C 3 (combination)
    for(int i = 0; i < wallList.size(); i++){
        for(int j = 0; j < i; j++){
            for(int k = 0; k < j; k++){
                a[wallList[i].first][wallList[i].second] = 1;
                a[wallList[j].first][wallList[j].second] = 1;
                a[wallList[k].first][wallList[k].second] = 1;
                ret = max(ret, solve());
                // 원상복구
                a[wallList[i].first][wallList[i].second] = 0;
                a[wallList[j].first][wallList[j].second] = 0;
                a[wallList[k].first][wallList[k].second] = 0;
            }
        }
    }
    cout << ret << "\n";
    return 0;
}

---

2636 치즈

문제 링크
dfs, bfs 로 해도 된다. 탐색만 필요하므로. 근데 가중치가 같고 최단거리를 구한다면 bfs로 해야한다~

#include <bits/stdc++.h>
using namespace std; 
int a[104][104], visited[104][104];
int dy[]={-1,0,1,0}, dx[] = {0,1,0,-1};   
int n,m,cnt,cnt2;
vector <pair<int,int>>v;
void go(int y,int x){
	visited[y][x] = 1;
    if(a[y][x]==1){ //이미 치즈가 있다면
        v.push_back({y,x});
        return; // 종료
    }
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny<0 || ny>=n || nx<0 || nx>=m || visited[ny][nx]) 
        	continue; 
        go(ny,nx);
    }
    return;
}


int main(){ 
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>a[i][j];
        }
    }
    while(true){
        cnt2 =0; // 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수
        fill(&visited[0][0],&visited[0][0] + 104 * 104,0);
        v.clear(); 
        go(0,0); 
        for(pair<int, int> b : v){
			cnt2++;
			a[b.first][b.second] = 0;
		}   
        bool flag = 0; // 치즈가 다 녹아버린 상태
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(a[i][j] != 0) flag = 1; // 치즈가 하나라도 있다면
            }
        }
        cnt++; // 치즈가 모두 녹아서 없어지는 데 걸리는 시간
        if(!flag) break;
    }
    cout<< cnt << "\n" << cnt2 << '\n'; 
}

---

4179 불! 🎯

문제 링크

문제 접근

병훈이가 불보다 빨리 뛰쳐나올 때의 최단거리를 구하는 문제이다.
가중치가 같은 그래프에서의 최단거리 👉 BFS

불의 최단거리와 지훈의 최단거리를 비교해서, (불보다) 지훈이가 더 빠르다면 전진하도록 한다.

또한 불은 여러개일 수 있고, 지훈은 한 명으로 고정되어있다.

반례

불이 아예 없다면 fire_check 라는 2차원 배열은 0의로 정의된다.
그래서 초기값으로 큰 값(여기서 INF)으로 초기화를 해줘야 한다.

전체 코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<tuple>
using namespace std;

const int INF = 987654321;
char a[1004][1004]; // 입력으로 주어지는 미로맵
int fire_check[1004][1004], person_check[1004][1004];
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };
int n, m, sx, sy, ret, x, y;

// 오버플로우 체크
bool in(int a, int b) {
	return 0 <= a && a < n && 0 <= b && b < m;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	queue<pair<int, int>> q;
	cin >> n >> m;
	fill(&fire_check[0][0], &fire_check[0][0] + 1004 * 1004, INF);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
			if (a[i][j] = 'F') {
				fire_check[i][j] = 1;
				q.push({ i,j });
			}
			else if (a[i][j] == 'J') {
				sy = i;
				sx = j;
			}
		}
	}

	// 불은 각 지점에서 네 방향으로 확산된다
	while (q.size()) {
		tie(y, x) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!in(ny, nx)) continue;
			if (fire_check[ny][nx] != INF || a[ny][nx] == '#') continue;
			fire_check[ny][nx] = fire_check[y][x] + 1;
			q.push({ ny,nx });
		}
	}

	person_check[sy][sx] = 1;
	q.push({ sy,sx });
	while (q.size()){
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		// 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다
		if (x == m - 1 || y == n - 1 || x == 0 || y == 0) {
			ret = person_check[y][x];
			break;
		}

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!in(ny, nx)) continue;
			if (person_check[ny][nx] || a[ny][nx] == '#') continue;
			// 불이 지훈이보다 빠르거나 같다면 지훈이는 갈 수 없다
			if (fire_check[ny][nx] <= person_check[y][x] + 1) continue;
			// 지훈이가 갈 수 있다면
			person_check[ny][nx] = person_check[y][x] + 1;
			q.push({ ny,nx });
		}
	}
	if (ret != 0) cout << ret << '\n';
	else cout << "IMPOSSIBLE\n";
	return 0;
}

---