이런 문제이고, 그래프고 파고들어갈 부분이기 때문에 BFS일 가능성이 커보인다
여러 가지 규칙을 찾아보고 조금 분석해봤지만
결론적으로는 이 문제의 핵심은 0,0, 즉 원점에서 아무것도 뚫지 않고 딱 닿을 수 있는 치즈조각을 하나씩 모아서 싹 없애는게 포인트라고 생각했다
그렇다면 정석적인 BFS 로직을 짜보자면
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int W, H;
cin >> H >> W;
vector<vector<int>> Cheese(H, vector<int>(W));
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
cin >> Cheese[i][j];
}
}
int time = 0;
int leftCheese = 0;
int dr[4] = { -1, 1, 0, 0 };
// 세로 변화량 잡아두기,
int dc[4] = { 0, 0, -1, 1 };
// 가로 변화량 잡아두기
while (true) {
//외부 공기 BFS를 위한 visited
//방문 체크용
vector<vector<int>> visited(H, vector<int>(W, 0));
//이번 시간에 녹을 치즈 위치 모으기
vector<pair<int, int>> melt;
queue<pair<int, int>> q;
//페어 큐를 만든 후
q.push({ 0, 0 });
//시작점에 0, 0 을 넣는다
visited[0][0] = 1;
// 방문에 체크
while (!q.empty()) {
//큐가 빌때까지 반복한다
pair<int, int> cur = q.front();
q.pop();
int h = cur.first;
int w = cur.second;
// 큐에서 하나 꺼내서 현재 위치를 h, w로 잡고
// 그 칸에서 4방향 탐색 시작
for (int k = 0; k < 4; k++) {
int nr = h + dr[k];
int nc = w + dc[k];
//위, 아래, 왼쪽, 오른쪽 이웃칸의 nr, nc 좌표 계산
if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
//범위 벗어나면 패스
if (visited[nr][nc]) continue;
// 방문했었으면 패스
if (Cheese[nr][nc] == 0) {
//공기면 계속 퍼짐
visited[nr][nc] = 1;
//방문 표시
q.push({ nr, nc });
//큐에 넣기
}
else if(Cheese[nr][nc] == 1) {
//치즈를 만나면 녹을 후보에 추가
//바로 0으로 바꾸면 안됨
visited[nr][nc] = 1;
//방문 표시
melt.push_back({ nr, nc });
//녹을 치즈 후보에 추가
}
}
}
if (melt.empty()) break; //더 이상 녹을 치즈가 없으면 종료
// 한꺼번에 녹이기
leftCheese = (int)melt.size();
for (int i = 0; i < (int)melt.size(); i++) {
// 녹이기
int h = melt[i].first;
// 녹일 좌표 h
int w = melt[i].second;
// 녹일 좌표 w
Cheese[h][w] = 0;
// 녹이기
}
time++;
// 시간 증가
}
cout << time << '\n' << leftCheese << '\n';
return 0;
}
이런식의 코드를 짜보았다
아직 BFS류의 코드에 약해서 한줄한줄 분석해보자면
우선 H, W를 만들고 치즈라는 2차원 벡터에 넣어서 기본적인 구조를 만들고 거기에 삽입을 했다
int W, H; cin >> H >> W; vector<vector<int>> Cheese(H, vector<int>(W)); for(int i = 0; i < H; i++) { for(int j = 0; j < W; j++) { cin >> Cheese[i][j]; } }그리고 time, leftCheese로 기본 구조를 잡았다
int time = 0; int leftCheese = 0;그리고 dr로 가로, 즉 x축 이동을 구하고 dy로 세로, 즉 y축 이동을 구한다
int dr[4] = { -1, 1, 0, 0 }; // 세로 변화량 잡아두기, int dc[4] = { 0, 0, -1, 1 }; // 가로 변화량 잡아두기그리고 이제 While true인 동안 일단 방문 체크를 위한 Cheese랑 똑같은 visited 벡터를 만들었다
while (true) { //외부 공기 BFS를 위한 visited //방문 체크용 vector<vector<int>> visited(H, vector<int>(W, 0));그리고 지금 이 순간에 녹을 치즈의 위치, melt 페어를 만들었다
vector<pair<int, int>> melt;그리고 페어 큐를 하나 더 만든 후 시작점에 0,0을 넣고 visited에도 0, 0 에 1, 즉 방문 표시를 한다
queue<pair<int, int>> q; //페어 큐를 만든 후 q.push({ 0, 0 }); //시작점에 0, 0 을 넣는다 visited[0][0] = 1; // 방문에 체크그래서 이 큐가 빌 때까지 반복을 하는데 또 cur라는 페어를 만드는데 q.front를 대입하고 q를 pop하면서 맨 앞에걸 쓰는 걸 명시한다
while (!q.empty()) { //큐가 빌때까지 반복한다 pair<int, int> cur = q.front(); q.pop();int h는 cur,즉 방금 나온 q.front의 first, w는 second를 넣고 결국 지금 현재 위치를 h, w로 잡고 4방향을 탐색한다
int h = cur.first; int w = cur.second;그리고 다시 4방향을 반복 탐색하는데 int nr는 높이 + dr[k]고 nc는 w + dc[k]로 적용해 구한다
for (int k = 0; k < 4; k++) { int nr = h + dr[k]; int nc = w + dc[k]; //위, 아래, 왼쪽, 오른쪽 이웃칸의 nr, nc 좌표 계산그리고 아래 범위는 그냥 주변 봤을 때 좌표 자체를 벗어나면 넘긴다
if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; //범위 벗어나면 패스방문했으면 넘긴다
if (visited[nr][nc]) continue; // 방문했었으면 패스일단 공기라면 계속 지나갈 수 있어 그리고 방문 표시를 하고 큐에 넣어,
그래야 반복문에 다시 대입해 다음 칸으로 가서 검사할 수 있기 때문if (Cheese[nr][nc] == 0) { //공기면 계속 퍼짐 visited[nr][nc] = 1; //방문 표시 q.push({ nr, nc }); //큐에 넣기 }그리고 치즈를 만나면 녹을 후보에 추가하고 방문 표시를 해 대신 바로 녹이면 안되고 melt라는 녹을 치즈 후보에 추가한다
else if(Cheese[nr][nc] == 1) { //치즈를 만나면 녹을 후보에 추가 //바로 0으로 바꾸면 안됨 visited[nr][nc] = 1; //방문 표시 melt.push_back({ nr, nc }); //녹을 치즈 후보에 추가 } }그리고 melt.empty, 즉 더 이상 녹일 치즈가 없으면 종료
if (melt.empty()) break; //더 이상 녹을 치즈가 없으면 종료leftCheese는 지금까지 녹이는 후보에 넣은 모든 좌표의 개수
leftCheese = (int)melt.size();그래서 저기에 대입하는거고 그리고 아래는 녹이는 과정
for (int i = 0; i < (int)melt.size(); i++) { // 녹이기 int h = melt[i].first; // 녹일 좌표 h int w = melt[i].second; // 녹일 좌표 w Cheese[h][w] = 0; // 녹이기 }그리고 time을 더하고 다음 껍질에 또 같은 과정을 돌린다
time++;다 한 후 돌린 시간과 마지막에 남은 leftcheese를 대입하면 끝
cout << time << '\n' << leftCheese << '\n'; return 0;
아무튼 이런 과정이다, 아마 기본적인 BFS 문제인거 같은데 지식 부족으로 도움을 많이 받았다, 공부가 필요해보이는 부분
