#include <bits/stdc++.h>
using namespace std;
int n, s1, s2;
vector<pair<int, int> > m[100001];
bool ch[100001];
bool flag = false;
void DFS(int x, int sum, int max_dist) {
if (flag) return;
if (x == s2) {
cout << sum - max_dist << '\n';
flag = true;
return;
}
for (int i = 0; i < m[x].size(); i++) {
int nx = m[x][i].first;
int nd = m[x][i].second;
if (ch[nx] == 0) {
ch[nx] = 1;
DFS(nx, sum + nd, max(nd,max_dist));
}
}
return;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s1 >> s2;
for (int i = 0; i < n - 1; i++) {
int a, b, c;
cin >> a >> b >> c;
m[a].push_back({ b,c });
m[b].push_back({ a,c });
}
ch[s1] = 1;
DFS(s1, 0, 0);
return 0;
}
d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우 서쪽을 나타낸다.
로봇 청소기는 다음과 같이 작동한다.
현재 위치를 청소한다.
현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
방향을 전환하면서 이동하면서 청소를 할 수 있는 방의 개수를 찾아야 하는 문제다.
2.접근 방법[알고리즘]
이 문제를 DFS를 통해 시뮬레이션을 할 때
종료 조건은 탐색할 수 있는 네 방향 모두 이미 청소되었거나 벽인 경우이고 후진을 할 수 없을 때다.
DFS를 돌면서 네방향 모두 체크해주고,
네방향 모두 이미 청소되었거나 벽이라면
후진을 시켜주고 후진을 할 수 없다면 종료를 시켜준다.
종료조건에 해당하지 않는다면
방향전환을 하고, 방향전환시 전진 했을 때 청소가 가능한 방이라면 전진을 시켜준다.
청소가 불가능 한 방이라면 전진하지 않는다.
해당 좌표가 이미 방문했던 점이라도 다시 방문해도 상관 없다
위 조건에만 만족하면 된다.
DFS코드
void DFS(int x, int y, int d) {
if (ended) return;
bool all_cleaned = true;
//네방향 확인
for (int i = 0; i < 4; i++) {
if (arr[x + dx[i]][y + dy[i]] == 0) {
all_cleaned = false;
break;
}
}
if (all_cleaned) {
// 벽이 있어서 후진 할 수 없다면 종료
if (arr[x - dx[d]][y - dy[d]] == -1) {
ended = true;
return;
}
else {
//후진이 가능할 때
DFS(x - dx[d], y - dy[d], d);
}
}
// 왼쪽으로 방향 회전
int nd = d == 0 ? 3 : d - 1;
int nx = x + dx[nd];
int ny = y + dy[nd];
if (arr[nx][ny] == 0) {
arr[nx][ny] = ++cleaned;
//청소 가능한 방이라면 방향전환후 전진
DFS(nx, ny, nd);
}
else {
//청소 불가능한 방이라면 방향전환만
DFS(x, y, nd);
}
}
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, r, c, d, arr[51][51], cleaned;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
bool ended = false;
void DFS(int x, int y, int d) {
if (ended) return;
bool all_cleaned = true;
//네방향 확인
for (int i = 0; i < 4; i++) {
if (arr[x + dx[i]][y + dy[i]] == 0) {
all_cleaned = false;
break;
}
}
if (all_cleaned) {
// 벽이 있어서 후진 할 수 없다면 종료
if (arr[x - dx[d]][y - dy[d]] == -1) {
ended = true;
return;
}
else {
//후진이 가능할 때
DFS(x - dx[d], y - dy[d], d);
}
}
// 왼쪽으로 방향 회전
int nd = d == 0 ? 3 : d - 1;
int nx = x + dx[nd];
int ny = y + dy[nd];
if (arr[nx][ny] == 0) {
arr[nx][ny] = ++cleaned;
DFS(nx, ny, nd);
}
else {
DFS(x, y, nd);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
cin >> r >> c >> d;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if (arr[i][j] == 1) {
arr[i][j] = -1;
}
}
}
arr[r][c] = ++cleaned;
DFS(r, c, d);
cout << cleaned;
return 0;
}
4. DFS를 돌면서 현재 좌표에 -1이 저장되어 있지 않다면 탈출이 가능한지 불가능한지 이미 구해졌으므로
그 값을 리턴해준다.
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
//방문한 곳을 다시 방문하면 종료
int n, m, ans, dy[503][503];
char arr[503][503];
int DFS(int x, int y) {
char a = arr[x][y];
// 미로 탈출
if (a == '\0') return 1;
int& cur = dy[x][y];
//x,y가 이미 방문한 점이라면
if (cur != -1) {
return cur;
}
// 방문 표시
cur = 0;
if (a == 'U') {
cur = DFS(x - 1, y);
}
else if (a == 'R') {
cur = DFS(x, y + 1);
}
else if (a == 'D') {
cur = DFS(x + 1, y);
}
else if (a == 'L') {
cur = DFS(x, y - 1);
}
return cur;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
dy[i][j] = -1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ans += DFS(i,j);
}
}
cout << ans <<'\n';
}
모든 영역은 비활성화 바이러스거나 활성화 바이러스거나 상관 없이 바이러스이기만 하면 된다.
문제풀이과정
1. DFS를 통해 m개의 비활성화 바이러스를 선택해 활성화 바이러스로 만든다.
2. 선택된 활성화바이러스로 BFS를 하고, 벽을 제외한 모든영역에 바이러스를 퍼트리는 시간을 구한다.
3. DFS를 돌며 m개를 다르게 선택하며 최소 시간을 구해준다.
4. 바이러스를 어떤 방법으로도 전체 영역에 퍼트릴 수 없다면 -1, 아니면 최소시간을 출력한다.
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, arr[51][51], ans=INT_MAX, total_zero;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool ch[51][51];
bool virus_select[11];
vector<pair<int, int> > virus;
queue<pair<int,int> > Q;
void BFS() {
int count_zero = 0;
//활성화된 바이러스 Q에 넣어줌
for (int i = 0; i < virus.size(); i++) {
if (virus_select[i] == 1) {
Q.push({ virus[i].first, virus[i].second});
ch[virus[i].first][virus[i].second] = 1;
}
}
int time = 0;
while (!Q.empty()) {
int cur_size = Q.size();
/*0인 영역에 바이러스를 다 퍼트렸는지 체크*/
if (total_zero == count_zero) {
ans = min(time, ans);
while (!Q.empty()) Q.pop();
break;
}
/*같은 시간에 새로 추가된 모든 바이러스를 BFS로 탐색*/
for (int j = 0; j < cur_size; j++) {
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 (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (arr[nx][ny] == -1) continue; //벽이면 continue
if (ch[nx][ny] == 0) { //비활성화된 바이러스, 0인 영역 모두 방문
ch[nx][ny] = 1;
Q.push({ nx, ny });
if (arr[nx][ny] == 0) count_zero++; //0인 영역을 방문한 거라면 0인 영역에 바이러스 퍼진 갯수 세줌
}
}
}
time++;
}
//DFS에서 또 ch를 사용하므로 BFS함수 이전 원래 상태로 초기화
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ch[i][j] = 0;
}
}
}
void DFS(int cur, int L) {
if (L == m) {
BFS();
}
else {
for (int i = cur; i < virus.size(); i++) {
virus_select[i] = 1;
DFS(i + 1, L + 1);
virus_select[i] = 0;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
if (arr[i][j] == 2) virus.push_back({ i,j });
else if(arr[i][j] == 0) total_zero++;
}
}
DFS(0, 0);
if (ans == INT_MAX) {
cout << -1;
}
else {
cout << ans;
}
}
백준 17142 연구소3 해결 메모리 및 시간
4.틀린 이유
1. 시간초과 이유 : 바이러스를 벽을 제외한 모든 영역에 퍼트렸는지 확인
/*0인 영역에 바이러스를 다 퍼트렸는지 체크*/
if (total_zero == count_zero) {
ans = min(time, ans);
while (!Q.empty()) Q.pop();
break;
}
0의 개수를 세는 변수를 따로 설정해 바이러스가 된 0의 개수를 세서 비교했다.
이전에는 n*n 배열을 모두 탐색해 0이 있는지 없는지 확인해서 시간초과가 나서 틀렸다.
2. 비활성화된 바이러스도 바이러스다.
처음에 문제를 잘 이해하지 못해 모든 바이러스를 활성화 시켜야 끝나는 줄 알고 그렇게 했는데
1. 백트래킹으로 바이러스 놓는 칸 m개 선택 2. m개를 선택했을 때 바이러스 다 퍼트릴 수 있는 지 BFS해보고 퍼트릴 수 있다면 시간을 구한다. 3. m개를 선택하는 모든 방법에 대하여 시간을 구해보고 최소 시간을 뽑는다. 4. 어떤 방법으로도 바이러스를 모든 공간에 퍼트릴 수 없다면 -1을 출력한다.
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, arr[51][51], ans=INT_MAX;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int > > virus;
queue<pair<int, int> > Q;
//1. 바이러스 놓는 칸 m개 선택
//2. 바이러스 다 퍼트렸는지 확인
//3. 다 퍼트렸다면 최소시간 확인
//4. 다 퍼트린게 없다면 -1 출력
void print() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == -1) cout << '-' << ' ';
else cout << arr[i][j] <<' ';
}
cout << '\n';
}
cout << "------------\n";
}
int check() {
int minute = 0;
//print();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == -1) continue;
if (arr[i][j] == 0) {
return INT_MAX;
}
else {
minute = max(arr[i][j], minute);
}
}
}
return minute;
}
void BFS() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == 1) {
Q.push({ i,j });
}
}
}
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 (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (arr[nx][ny] == 0) {
arr[nx][ny] = arr[x][y] + 1;
Q.push({ nx,ny });
}
}
}
}
void initialize() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] > 1) {
arr[i][j] = 0;
}
}
}
}
void DFS(int cur, int L) {
if (L == m) {
BFS();
ans = min(ans, check());
initialize();
}
else {
for (int i = cur; i < virus.size(); i++) {
//바이러스는 arr에서 1로 체크해준다.
int x = virus[i].first;
int y = virus[i].second;
if (arr[x][y] == 0) {
arr[x][y] = 1;
DFS(i + 1, L + 1);
arr[x][y] = 0;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
queue<pair<int, int > > Q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
if (arr[i][j] == 1) {
arr[i][j] = -1;
}
if (arr[i][j] == 2) {
arr[i][j] = 0;
virus.push_back({ i,j });
}
}
}
DFS(0,0);
if (ans == INT_MAX) {
cout << -1;
}
else {
cout << ans-1;
}
}
int Count() {
BFS();
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) cnt++;
else if (arr[i][j] == 2) {
//arr배열을 재사용하기위해 BFS 돌아서 바이러스가 퍼진 영역을
//다시 0으로 만들어준다.
arr[i][j] = 0;
}
}
}
//바이러스 초기화 arr 원상태로 만들어줌
for (int i = 0; i < virus.size(); i++)
arr[virus[i].first][virus[i].second] = 2;
return cnt;
}
Count를 다 하고 나면 arr배열에 초기 입력값을 그대로 저장해준다.
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, arr[10][10], ans;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int> > virus;
queue<pair<int, int > > Q;
// 바이러스 퍼트리는 함수
void BFS() {
for (int i = 0; i < virus.size(); i++) {
Q.push({ virus[i].first, virus[i].second });
}
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 (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (arr[nx][ny] == 0) {
//바이러스가 퍼질 수 있는 곳이면 바이러스로 만들어준다.
arr[nx][ny] = 2;
Q.push({ nx,ny });
}
}
}
}
//0 갯수 세는 함수
int Count() {
BFS();
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) cnt++;
else if (arr[i][j] == 2) {
//arr배열을 재사용하기위해 BFS 돌아서 바이러스가 퍼진 영역을
//다시 0으로 만들어준다.
arr[i][j] = 0;
}
}
}
//바이러스 초기화 arr 원상태로 만들어줌
for (int i = 0; i < virus.size(); i++)
arr[virus[i].first][virus[i].second] = 2;
return cnt;
}
void DFS(int x, int y, int L) {
if (L == 3) {
//바이러스 BFS 돌고 0 갯수 새기
ans = max(ans, Count());
}
else {
// 벽 만들기 백트래킹
for (int i = x; i < n; i++, y=0) {
for (int j = y; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
DFS(i, j, L + 1);
arr[i][j] = 0;
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if (arr[i][j] == 2) {
virus.push_back({ i,j });
}
}
}
DFS(0, 0, 0);
cout << ans << '\n';
}
