(모르겠음 외워)
문제
문제링크
문제
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.
<그림 1> 원래 치즈 모양
다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.
<그림 2> 한 시간 후의 치즈 모양
<그림 3> 두 시간 후의 치즈 모양
<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.출력
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.예제 입력 1
13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
예제 출력 1
3
5
바쁜 현대인을 위해 3줄요약 하자면 바깥쪽 1을 모두 0으로 바꿔주는 알고리즘이다 다시말해 0과 맞닿아 있는 부분을 0으로 차례차례 바꿔주면 되는 알고리즘이다
방법 1. DFS알고리즘을 활용한 풀이
//백준 2636 치즈 #include <iostream> #include <algorithm> #include <vector> using namespace std; int a[104][104], visited[104][104]; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; int n, m, cnt, cnt2; vector<pair<int, int>> v; void go(int x, int y) { visited[x][y] = 1; if (a[x][y] == 1) // 만약 a[x][y]가 치즈면 { v.push_back({ x, y }); //push_back()을 통해 벡터 v에 매개변수 x와 y를 넣고 return; // dfs 종료 } for (int i = 0; i < 4; i++) // 상하좌우 4개 일반적인 dfs, bfs { int nx = dx[i] + x; int ny = dy[i] + y; //ny < 0 || ny >= n || nx < 0 || nx >= m "overflow 처리" if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) continue; go(nx, ny); } 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) // 치즈가 녹고 확인하고 치즈가 녹고 확인하고, 1/0 반복 확인을 위해 while(true) { cnt2 = 0; fill(&visited[0][0], &visited[0][0] + 104 * 104, 0); //초기화(test case마다 초기화가 중요함) v.clear(); //녹아져야할 1을 한공간(vector v)에 담아서 한번에 녹임 go(0, 0); //끝지점 기반으로(0, 1)(1, 0)도 상관없긴 함 for (pair<int, int> b : v) { cnt2++; //모두 녹기전 한시간전에 남아있는 치즈조각 체크 a[b.first][b.second] = 0; //치즈를 없앤다(녹인다) -> 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++; // 치즈를 녹이기 위해 몇번의 go함수를 실행했냐 if (!flag) break; // 치즈가 다 녹으면 flag로 break } cout << cnt << "\n" << cnt2 << "\n"; return 0; }
2. BFS알고리즘을 활용한 풀이
#include <iostream> #include <vector> #include <queue> using namespace std; int a[104][104]; // a[i][j]가 0이면 녹일 치즈 없고, a[i][j]가 1이면 녹일 치즈가 있는거 int n, m; vector<pair<int, int>> cheese; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; bool is_inside(int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m); } void bfs() { queue<pair<int, int>> q; vector<pair<int, int>> to_melt; q.push({0, 0}); vector<vector<bool>> visited(n, vector<bool>(m, false)); visited[0][0] = true; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (is_inside(nx, ny) && !visited[nx][ny]) { if (a[nx][ny] == 0) { visited[nx][ny] = true; q.push({nx, ny}); } else { to_melt.push_back({nx, ny}); } } } } for (const pair<int, int>& p : to_melt) { a[p.first][p.second] = 0; } } 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] == 1) { cheese.push_back({i, j}); } } } int time = 0; int last_cheese = 0; while (!cheese.empty()) { last_cheese = cheese.size(); bfs(); time++; vector<pair<int, int> >::iterator it = cheese.begin(); while (it != cheese.end()) { int x = it->first; int y = it->second; if (a[x][y] == 1) { it++; } else { it = cheese.erase(it); } } } cout << time << "\n" << last_cheese << "\n"; return 0; }
주의!!!!!!!!!!
내일당장 C++로 코테보지 않는 사람은 절대 아래 코드를 보지 마시오!
모르면 외우자
다음과 같은 형식이 바로 BFS와 DFS다
1. DFS
for (int i = 0; i < 4; i++) // 상하좌우 4개 일반적인 dfs, bfs { int nx = dx[i] + x; int ny = dy[i] + y; //ny < 0 || ny >= n || nx < 0 || nx >= m "overflow 처리" if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) continue; go(nx, ny); }
2. BFS
void bfs() { queue<pair<int, int>> q; // 정수 쌍 저장하는 queue생성 및 BFS탐색에 사용 vector<pair<int, int>> to_melt; // 녹은 치즈를 저장하는 벡터 q.push({0, 0}); // 시작지점 (0, 0)을 queue에 넣음 vector<vector<bool>> visited(n, vector<bool>(m, false)); // 방문여부 나타내는 2차원 벡터 생성 visited[0][0] = true; //(0,0)을 시작지점으로, 시작지점을 true로 바꿈 while (!q.empty()) { // queue가 비어질때까지 무한반복! int x = q.front().first; // queue의 맨 앞 요소의 첫 번째 값을 x좌표 넣어 int y = q.front().second; // queue의 맨 앞 요소의 두 번째 값을 y좌표에 넣어 q.pop(); // queue의 맨 앞 요소 제거 for (int i = 0; i < 4; i++) { // 상/하/좌/우 네방향 탐색 int nx = x + dx[i]; // nx라는 새로운 좌표에 x와 {0, 0, 1, -1} 값중 하나 더해서 nx에 대입 int ny = y + dy[i]; // ny라는 새로운 좌표에 y와 {1, -1, 0, 0} 값중 하나 더해서 ny에 대입 // 자 까먹었을거 알고 bool is_inside(int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m); } // 이겁니다 if (is_inside(nx, ny) && !visited[nx][ny]) { // is_insied는 방금 위에서 선언한 nx, ny가 범위 내에 있고, !visited는 아직 방문 안했으면 if (a[nx][ny] == 0) { // 그래서 방문 했는데 어? 0이네? visited[nx][ny] = true; // 그럼 1로바꿔! q.push({nx, ny}); // 그리고 queue에 nx랑 ny 넣어(int nx = x + dx[i]) } else { // 방문했는데 1이네? to_melt.push_back({nx, ny}); // 1인거 to_melt 벡터에 전부 집어넣어 } } } } for (const pair<int, int>& p : to_melt) { // 1인거 찾고 a[p.first][p.second] = 0; // 0으로 바꾸고 } }
내가 내일 당장 코테인데 할줄아는 알고리즘이 하나도 없다? 이거라도 외우세요 그냥 코드 전체를 통으로
