https://www.acmicpc.net/problem/1726

1.문제설명

명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다

명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

동에서 서, 북에서 남으로 회전하는 데는 명령을 두번 해야한다

현재 방향에서 한 번의 명령으로 최대 3칸까지 이동이 가능하다.

벽을 통과할 수는 없다.

2.접근방법[알고리즘]

이 문제는 시작 지점에서 종료 지점 까지 가는데 필요한 최소 명령의 수를 구해야 한다.

한 번의 명령마다 방향전환을 하거나 이동을 한다.

특정 지점을 방문했을 때 단순히 좌표만 저장 하는 게 아니라, 방향에 대한 정보까지 저장을 해주어야한다.

그래서 이전에 방문했는지 체크해주는 배열을 3차원 배열로 만들어

vis[x][y][동 or 서 or 남 or 북] x, y 좌표에 대해서

동, 서, 남 , 북 방향 상태까지 필요햔 명령의 수를 체크해야한다.

하나의 좌표마다 행동할 수 있는 경우의 수는

현재 방향에서 1칸, 2칸, 3칸 이동하기와

현재 방향을 제외한 나머지 방향으로 방향전환 하기가 있다.

한 번의 명령으로 1칸 2칸 3칸 모두 이동하는 게 가능하지만,

방향을 전환 하는데는 동에서 서로 방향을 전환하거나 남에서 북으로 방향을 전환한다면 2번의 명령이 필요하다.

이 때 2번의 명령이 필요한 경우 방향을 전환했다고 바로 방문을 했다고 체크하는 게 아니라 

나중에 큐에서 나올 때 체크해주어야한다.

왜냐하면 x,y가 도착지점일 때 x,y에서 방향을 전환하는데 2번 명령을 하는 동안

다른 점에서 한번만에 도착하는 경우도 있기 때문이다.

결과적으로 도착점까지 최소 명령의 수를 구해야하기 때문에 우선순위 큐를 이용했다.

명령의 수를 최소힙으로 계속 pop해주면서 로봇이 최소 명령으로 하는 행동을 먼저하게 한다.

그러다 도착지점에 다다르면 바로 해당 도착지점에 오기까지 필요했던 명령의 수를 바로 리턴해주었다.

우선순위큐를 사용하지 않으면?

만약 우선순위큐를 사용하지 않는다면

도착지점에 도착했다고 바로 리턴해주면 안된다.

방향전환하는데 명령이 2번 일어나는 경우도 있어서

큐에서 뒤에 나오는 경우가 더 적은 명령의 수로 일어나는 행동일 수도 있기 때문이다.

즉 BFS를 돌지만 다른 문제와 다르게 큐에서 뒤에서 나오는 결과가 정답일 수도 있다.

3.문제풀이코드

첫 정답코드

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

//회전시키는데 명령 1, 현재 방향에서 이동하는데 명령 1,

int n, m, arr[105][105], sx, sy, sd, ex, ey, ed, ans = INT_MAX;
bool vis[105][105][5]; //1동 2서 3남 4북 방향 정보까지 받는다 

struct Edge {
	int x, y, d, cnt;
	Edge(int a, int b, int c, int e) {
		x = a;
		y = b;
		d = c;
		cnt = e;
	}
	bool operator<(const Edge& bb) const {
		return cnt > bb.cnt;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	priority_queue<Edge> Q;

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	cin >> sx >> sy >> sd;
	cin >> ex >> ey >> ed;

	vis[sx][sy][sd] = 1;
	Q.push(Edge(sx, sy, sd, 0));


	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int d = Q.top().d;
		int cnt = Q.top().cnt;
		Q.pop();
		vis[x][y][d] = 1;

		//if(d==1)
		//	cout << x <<' ' << y << " " << "동" << " " << cnt<< '\n';
		//else if(d==2)
		//	cout << x << ' ' << y << " " << "서" << " " << cnt<< '\n';
		//else if (d == 3)
		//	cout << x << ' ' << y << " " << "남" << " " << cnt<< '\n';
		//else if (d == 4)
		//	cout << x << ' ' << y << " " << "북" << " " << cnt<< '\n';

		if (x == ex && y == ey && d == ed) {
			ans = min(cnt, ans);
		}

		// 현재 방향에서 이동
		// d == 1 : nx : 0 / ny : 1, 2, 3
		// d == 2 : nx : 0 / ny : -1, -2, -3;
		// d == 3 : nx: 1 , 2 , 3 / ny : 0
		// d == 4 : nx : -1 -2 -3 / ny : 0;

		if (d == 1) {
			for (int i = 1; i <= 3; i++) {
				if (y + i > m) break;
				if (arr[x][y + i] == 1) break;
				if (vis[x][y + i][d] == 0) {
					vis[x][y + i][d] = 1;
					Q.push(Edge{ x,y + i,d ,cnt + 1 });
				}
			}
		}
		else if (d == 2) {
			for (int i = 1; i <= 3; i++) {
				if (y - i < 1) break;
				if (arr[x][y - i] == 1) break;
				if (vis[x][y - i][d] == 0) {
					vis[x][y - i][d] = 1;
					Q.push(Edge{ x,y - i,d ,cnt + 1 });
				}
			}
		}
		else if (d == 3) {
			for (int i = 1; i <= 3; i++) {
				if (x + i > n) break;
				if (arr[x + i][y] == 1) break;
				if (vis[x + i][y][d] == 0) {
					vis[x + i][y][d] = 1;
					Q.push(Edge{ x + i,y,d ,cnt + 1 });
				}
			}
		}
		else if (d == 4) {
			for (int i = 1; i <= 3; i++) {
				if (x - i < 1) break;
				if (arr[x - i][y] == 1) break;
				if (vis[x - i][y][d] == 0) {
					vis[x - i][y][d] = 1;
					Q.push(Edge{ x - i,y,d ,cnt + 1 });
				}
			}
		}

		//방향전환 명령 
		for (int i = 1; i <= 4; i++) {
			if (i == d) continue;

			if (vis[x][y][i] == 0) {
				if ((d == 1 && i == 2) || (d == 2 && i == 1)) {
					Q.push(Edge(x, y, i, cnt + 2));
				}
				else if ((d == 3 && i == 4) || (d == 4 && i == 3)) {
					Q.push(Edge(x, y, i, cnt + 2));
				}
				else {
					vis[x][y][i] = 1;
					Q.push(Edge(x, y, i, cnt + 1));
				}
			}
		}
	}

	cout << ans;
	return 0;

}

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

//회전시키는데 명령 1, 현재 방향에서 이동하는데 명령 1,

int n, m, arr[105][105], sx, sy, sd, ex, ey, ed, ans = INT_MAX;
bool vis[105][105][5]; //1동 2서 3남 4북 방향 정보까지 받는다 


struct Edge {
	int x, y, d, cnt;
	Edge(int a, int b, int c, int e) {
		x = a;
		y = b;
		d = c;
		cnt = e;
	}
	bool operator<(const Edge& bb) const {
		return cnt > bb.cnt;
	}
};

priority_queue<Edge> Q;



void move(int x, int y, int d, int cnt) {
	if (d == 1) {
		for (int i = 1; i <= 3; i++) {
			if (y + i > m) break;
			if (arr[x][y + i] == 1) break;
			if (vis[x][y + i][d] == 0) {
				vis[x][y + i][d] = 1;
				Q.push(Edge{ x,y + i,d ,cnt + 1 });
			}
		}
	}
	else if (d == 2) {
		for (int i = 1; i <= 3; i++) {
			if (y - i < 1) break;
			if (arr[x][y - i] == 1) break;
			if (vis[x][y - i][d] == 0) {
				vis[x][y - i][d] = 1;
				Q.push(Edge{ x,y - i,d ,cnt + 1 });
			}
		}
	}
	else if (d == 3) {
		for (int i = 1; i <= 3; i++) {
			if (x + i > n) break;
			if (arr[x + i][y] == 1) break;
			if (vis[x + i][y][d] == 0) {
				vis[x + i][y][d] = 1;
				Q.push(Edge{ x + i,y,d ,cnt + 1 });
			}
		}
	}
	else if (d == 4) {
		for (int i = 1; i <= 3; i++) {
			if (x - i < 1) break;
			if (arr[x - i][y] == 1) break;
			if (vis[x - i][y][d] == 0) {
				vis[x - i][y][d] = 1;
				Q.push(Edge{ x - i,y,d ,cnt + 1 });
			}
		}
	}
}

void turn_dir(int x, int y, int d, int cnt) {
	for (int i = 1; i <= 4; i++) {
		if (i == d) continue;
		if (vis[x][y][i] == 0) {
			if ((d == 1 && i == 2) || (d == 2 && i == 1)) {
				// 바로 방문 체크를 하면 안된다. 방향전환 하는 동안 먼저 방문하는 경우가 있을 수도 있다.
				Q.push(Edge(x, y, i, cnt + 2));
			}
			else if ((d == 3 && i == 4) || (d == 4 && i == 3)) {
				Q.push(Edge(x, y, i, cnt + 2));
			}
			else {
				vis[x][y][i] = 1;
				Q.push(Edge(x, y, i, cnt + 1));
			}
		}
	}
}


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];
		}
	}
	cin >> sx >> sy >> sd;
	cin >> ex >> ey >> ed;

	vis[sx][sy][sd] = 1;
	Q.push(Edge(sx, sy, sd, 0));

	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int d = Q.top().d;
		int cnt = Q.top().cnt;
		Q.pop();
		vis[x][y][d] = 1;

		if (x == ex && y == ey && d == ed) {
			cout << cnt;
			return 0;
		}
		// 현재 방향에서 이동
		move(x, y, d, cnt);
		//방향전환 명령 
		turn_dir(x,y,d,cnt);
	}

	return 0;

}

4. 반례모음

백준 1726 로봇 문제 반례 및 테스트케이스 모음입니다.

5 6
0 0 0 0 0 0
0 1 1 0 1 0
0 1 0 0 0 0
0 0 1 1 1 0
1 0 0 0 0 0
4 2 3
1 6 2

답 : 8

42 79
0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0
0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 0 0 1 0 0
1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0
1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 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 1 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0
0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1
1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0
1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 1
1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0
1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0
0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0
0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0
1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0
1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1
0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1
1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
1 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0
0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1
0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1
0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1
1 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0
0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1
0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0
0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0
0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1
1 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0
1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1
1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0
6 77 1
36 1 3

답 : 93

5 6
0 0 0 0 0 0
0 1 1 1 1 1
0 1 0 1 0 0
0 0 0 1 1 0
0 1 0 0 0 0
1 1 1
3 5 3

답 13

3 3
0 0 0
0 0 0
0 0 0
1 1 2
3 3 4

답 5

9 12
0 0 0 0 0 0 0 0 0 0 0 1
0 1 1 1 1 0 0 1 1 1 1 0
0 0 0 0 0 0 0 1 1 1 1 0
0 1 1 1 1 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 1 1 1 1 0
0 1 1 1 1 0 0 0 0 0 0 0
0 1 1 1 1 0 0 1 1 1 1 0
1 0 0 0 0 0 0 0 0 0 0 0
1 1 3
9 12 3

답 10

https://www.acmicpc.net/problem/14923

문제 설명

https://dingcoding.tistory.com/95

백준 2206번 벽부수고 이동하기 문제와 똑같은 문제다.

벽을 부순 상태와 부수지 않은 상태를 나누어서 생각해야 한다.

설명은 위 링크를 참고

문제풀이코드 C++

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

int n, m, hx, hy, ex, ey, arr[1003][1003], vis[1003][1003][2];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

struct Edge {
	int x, y, op;
	Edge(int a, int b, int c) {
		x = a;
		y = b;
		op = c;
	}
};

void print() {
	for (int k = 1; k >= 0; k--) {
		if (k == 1) {
			cout << "벽 뚫기 전 \n";
		}
		else {
			cout << "벽 뚫은 후 \n";
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << vis[i][j][k] << ' ';
			}
			cout << '\n';
		}
	}
	cout << "\n";
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	queue<Edge> Q;
	cin >> n >> m;
	cin >> hx >> hy;
	cin >> ex >> ey;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	vis[hx][hy][1] = 1;
	Q.push(Edge(hx, hy, 1));

	while (!Q.empty()) {
		int x = Q.front().x;
		int y = Q.front().y;
		int op = Q.front().op;
		Q.pop();

		/*print();*/

		if (x == ex && y == ey) {
			if (vis[x][y][1] == 0) {
				cout << vis[x][y][0]- 1;
			}
			else cout << vis[x][y][1] -1 ;
			return 0;
		}

		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 (op == 1) {
				if (arr[nx][ny] == 0 && vis[nx][ny][1]==0) {
					vis[nx][ny][1] = vis[x][y][1] + 1;
					//벽 방문 가능
					Q.push({ nx,ny,1 });
				}
				else if (arr[nx][ny] == 1) {
					vis[nx][ny][0] = vis[x][y][1] + 1;
					//이제 벽 방문 기회 없음 
					Q.push({ nx,ny,0 });
				}
			}
			else {//벽 뚫을 기회 없음 무조건 0으로만 다녀야함
				if (arr[nx][ny] == 0 && vis[nx][ny][0] == 0) {
					vis[nx][ny][0] = vis[x][y][0] + 1;
					Q.push({ nx,ny,0 });
				}
			}
		}



	}


	cout << -1;

	return 0;
}

https://www.acmicpc.net/problem/2206

1.문제설명

6 4
0100
1110
1000
0000
0111
0000

0은 이동할 수 있는 곳이고 1은 벽이다.

벽을 한번 부술 수 있을 때 (1,1)에서 (N,M) 까지 이동하는 최단 거리를 구해야한다.

2.접근방법[알고리즘]

맨 처음에는 없앨 벽을 선택하고, 그에 따른 최단 거리를 구해줬다.

하지만 이러면 계산량이 많아져서 시간초과가 된다.

https://www.acmicpc.net/board/view/27386

백준 게시판에 좋은 글이 있어서 첨부합니다.

요약하자면 벽을 부수기 전과 부순 후를 나누어서 생각해야 합니다.

이동하면서 현재 좌표는 벽을 부술 수 있는 지 없는지 상태를 저장해야합니다.

또 벽을 안 부수면서 이동할 때의 방문 기록을 체크해주는 배열과

벽을 부순 후 방문 기록을 체크해주는 배열을 따로 분리해 생각해야 합니다.

6 4
0100
1110
1000
0000
0111
0000

위 예제에 대해서 벽을 뚫기 전과 벽을 뚫은 이후를 따로 체크해주는 배열에 거리를 저장했습니다.

int vis[1003][1003][2];
//vis[x][y][1 = 벽 뚫을 기회 1번 있음] , vis[x][y][0 = 벽 뚫을 기회 x]

위와 같은 방문기록을 체크해주는 vis 배열을 3차원으로 만들어

vis[x][y][1 == 벽을 뚫을 기회가 1번 있는 상태]

vis[x][y][0 == 벽을 뚫을 기회가 없는 상태, 이미 벽을 한번 뚫은 상태]

이렇게 저장해주어 BFS를 돌면서

벽을 뚫기 전까지는 vis[x][y][1]에 방문기록을 저장하다가

벽을 뚫는 일이 발생하면 그 이후부터는 vis[x][y][0]에 방문 기록을 저장해줍니다.

3.문제풀이코드 C++

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

int n, m;
string arr[1003];
int vis[1003][1003][2];
//vis[x][y][1 = 벽 뚫을 기회 1번 있음] , vis[x][y][0 = 벽 뚫을 기회 x] 
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//void print() {
//	for (int k = 1; k >= 0; k--) {
//		if (k == 1) {
//			cout << "벽 뚫기 전 \n";
//		}
//		else {
//			cout << "벽 뚫은 후 \n";
//		}
//		for (int i = 0; i < n; i++) {
//			for (int j = 0; j < m; j++) {
//				cout << vis[i][j][k] << ' ';
//			}
//			cout << '\n';
//		}
//	}
//	cout << "\n";
//}

struct Edge {
	int x, y, op;
	Edge(int a, int b, int c) {
		x = a;
		y = b;
		op = c;
	}
};


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	queue<Edge> Q;
	Q.push(Edge(0,0,1));
	// 0에 좌표 방문 저장, 1에 벽 부쉇는지 저장 
	vis[0][0][1] = 1;
	vis[0][0][0] = 0;

	while (!Q.empty()) {
		int x = Q.front().x;
		int y = Q.front().y;
		int op = Q.front().op;
		Q.pop();

		//print();

		if (x == n - 1 && y == m - 1) {
			//도착 점 방문 시 이동하는데 걸린 거리 출력 
			if (vis[n - 1][m - 1][0] == 0)
				cout << vis[n - 1][m - 1][1];
			else
				cout << vis[n - 1][m - 1][0];
			return 0;
		}

		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 (op == 1) {
				//벽 부순적 없음 1도 방문 가능
				if (vis[nx][ny][1] == 0) {
					// 0 방문 할 떄 
					if (arr[nx][ny] == '0') {
						Q.push(Edge(nx, ny, 1));
						vis[nx][ny][1] = vis[x][y][1] + 1;
					}
					else { // 1 방문할 떄 
						Q.push(Edge(nx, ny, 0));
						vis[nx][ny][0] = vis[x][y][1] + 1;
					}
				}
			}
			else {
				//벽 부순적 있음 
				//
				if (vis[nx][ny][0] == 0 && vis[nx][ny][1]==0) {
					if (arr[nx][ny] == '0') {
						Q.push(Edge(nx, ny, 0));
						vis[nx][ny][0] = vis[x][y][0] + 1;
					}
				}

			}
		}
	}

	cout << -1;
	return 0;
}

4. 2206 반례 

백준 2206번 벽부수기 반례, 테스트케이스 모음입니다.

1.

5 8
01000000
01010000
01010000
01010011
00010010

2.

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

3.

3 3
011
111
110

4.

6 7
0000000
0111111
0100010
0101010
0101010
0001010

https://www.acmicpc.net/problem/3055

1.문제설명

3 6
D...*.
.X.X..
....S.

물은 상하좌우로 퍼진다. 고슴도치는 상하좌우로 한 칸 씩 이동할 수 있다

X는 물, 고슴도치 모두 지날 수 없다

D는 고슴도치만 갈 수 있다.

고슴도치가 물을 피해 D로 갈 수 있다면 최소 시간을 출력하고,

그럴 수 없다면 문제에서 제시한 문자열을 출력해준다.

2.접근 방법[알고리즘]

1. 물을 상하좌우로 퍼트린다.

2. 고슴도치를 물이 없는 곳으로 상하좌우 이동시킨다.

3. 1,2를 반복하면서 고슴도치가 D를 방문하면 시간을 출력하고 종료한다.

4. D를 방문할 수 없으면 "KAKTUS" 를 출력한다.

이 문제에서 물과 고슴도치 모두 BFS를 동시에 해주어야 한다.

각각의 큐를 만들고 시간을 증가시키면서 새로 방문한 노드에 대해서 일괄적으로 상하좌우 탐색한다.

고슴도치는 물이 방문할 점을 방문할 수 없기 때문에

물 -> 고슴도치 -> 물 -> 고슴도치 순으로 BFS를 돈다.

3.문제풀이코드 C++

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

int r, c;
char arr[53][53];
bool s_check[53][53], wt_check[53][53];
int ch[53][53];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
//물 먼저 이동 후 고슴도치 이동

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> r >> c;
	queue<pair<int, int> > wt;
	queue<pair<int, int> > s;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == '*') {
				ch[i][j] = -1;
				wt.push({ i,j });
				wt_check[i][j] = 1;
			}
			else if (arr[i][j] == 'S') {
				ch[i][j] = 1;
				s.push({ i,j });
				s_check[i][j] = 1;
			}
			else if (arr[i][j] == 'X') {
				ch[i][j] = 2;
			}
			else if (arr[i][j] == 'D') {
				ch[i][j] = 3;
			}
		}
	}
	int t = 0;
	while (true) {

		int s_size = s.size();
		int wt_size = wt.size();

		if (s_size == 0) break;

		for (int i = 0; i < wt_size; i++) {
			int x = wt.front().first;
			int y = wt.front().second;
			wt.pop();

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx <= 0 || nx > r || ny <= 0 || ny > c||wt_check[nx][ny] == 1) continue;
				if (ch[nx][ny] == 0 || ch[nx][ny]==1) {
					wt_check[nx][ny] = 1;
					ch[nx][ny] = -1;
					wt.push({ nx,ny });
				}
			}
		}

		for (int i = 0; i < s_size; i++) {
			int x = s.front().first;
			int y = s.front().second;
			s.pop();

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if (nx <= 0 || nx > r || ny <= 0 || ny > c || s_check[nx][ny] == 1) continue;
				if (ch[nx][ny] == 0 || ch[nx][ny] == 1 ) {
					ch[nx][ny] = 1;
					s_check[nx][ny] = 1;
					s.push({ nx,ny });
				}
				else if (ch[nx][ny] == 3) {
					cout << t+1;
					return 0;
				}
			}

		}
		t++;
		//print();
	}

	cout << "KAKTUS" << '\n';

	return 0;
}

틀린이유

처음에 고슴도치와 물이 방문한 좌표를 체크해주지 않아 틀렸다

BFS든 DFS든 방문해준 점을 체크표시해주지 않으면 방문한 곳을 계속 방문해서 무한 루프에 빠지고 만다.

그로 인해 시간초과나 메모리초과가 발생한다.

https://www.acmicpc.net/problem/17090

1.문제설명

3 4
RRDD
RRDR
DULU

모든 점에 대해서 각 점으로부터 출발 할 때

다음 규칙으로 이동하여 미로 밖으로 탈출할 수 있는 점의 개수를 구하는 문제다.

이동 과정을 나타냈을 때 빨간색 같은 경우는 탈출할 수 없고

파란색은 탈출 할 수 있는 경로이다.

위 미로의 특성 상 같은 경로 상에 있다면 같은 결괏값을 가지게 된다.

2. 접근방법[알고리즘]

DFS로 메모리제이션을 해주면서 탈출할 수 있는지 없는지를 구해주어야한다.

1.DFS를 수행하기전 초기값으로 모든 좌표에 -1을 저장한다.

2.DFS를 수행하면서 방문한 점에는 0을 저장한다.

3.DFS 수행 결과 탈출에 성공한다면 탈출 경로까지 지나는 모든 점에 1을 저장한다.

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';
}

시간 초과 이유

지나가는 점에 대해서도 결괏값을 저장해주어야 하는데,

점 하나 하나 for 문을 돌 때마다 따로 처리해줘서 시간이 초과되었다.

메모리제이션이 중요한 문제다.

https://www.acmicpc.net/problem/17142

1.문제설명

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다.

0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다.

2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

2는 비활성화된 바이러스를 의미하고 2 중에서 m개를 선택해 바이러스를 활성화시킬 때

벽을 제외한 모든 영역이 바이러스가 되는 최소 시간을 구해야한다.

2.문제접근[알고리즘]

https://dingcoding.tistory.com/90

https://dingcoding.tistory.com/91

연구소 3번 문제는 연구소 1번 2번 문제와 비슷하나 가장 중요한 차이점은

초기에 모든 바이러스는 비활성화 상태라는 점이다.

문제에서 m개의 비활성화 바이러스를 선택해

벽을 제외한 모든 영역이 바이러스가 되는 최소 시간을 구해야한다.

모든 영역은 비활성화 바이러스거나 활성화 바이러스거나 상관 없이 바이러스이기만 하면 된다.

문제풀이과정

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;
	}

}

4.틀린 이유

1. 시간초과 이유 : 바이러스를 벽을 제외한 모든 영역에 퍼트렸는지 확인

/*0인 영역에 바이러스를 다 퍼트렸는지 체크*/
		if (total_zero == count_zero) {
			ans = min(time, ans);
			while (!Q.empty()) Q.pop();
			break;
		}

0의 개수를 세는 변수를 따로 설정해 바이러스가 된 0의 개수를 세서 비교했다.

이전에는 n*n 배열을 모두 탐색해 0이 있는지 없는지 확인해서 시간초과가 나서 틀렸다.

2. 비활성화된 바이러스도 바이러스다.

처음에 문제를 잘 이해하지 못해 모든 바이러스를 활성화 시켜야 끝나는 줄 알고 그렇게 했는데

비활성화 여부와 관계없이 모든 영역이 바이러스로 바뀌어있으면 BFS를 종료하면 된다.

https://www.acmicpc.net/problem/17141

1.문제설명

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

N*N 정사각형 배열이 주어진다. 1은 바이러스가 지나갈 수 없는 벽을 의미한다.

m은 바이러스를 놓을 수 있는 개수이고, 2는 바이러스를 놓을 수 있는 공간이다.

2가 바이러스가 놓여진 게 아니라 놓을 수 있는 공간인 점이 중요하다.

m개의 바이러스를 2가 쓰여진 공간에 두었을 때 

벽을 제외한 모든 공간에 바이러스를 퍼트린다면 

바이러스를 퍼트리는데 걸리는 최소 시간을 구해야한다.

그 최소 시간을 출력해야한다.

만약 바이러스 m개를 어떻게 두어도 벽을 제외한 모든 공간에 바이러스를 퍼트리지 못한다면

-1을 출력한다.

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;
	}

}

https://www.acmicpc.net/problem/14502

1.문제설명

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

0은 빈공간이고 1은 벽이고 2는 바이러스다.

바이러스는 상하좌우로 퍼질수 있고 벽은 통과할 수 없다.

벽을 3개 설치해서 바이러스가 퍼지지 않는 빈공간(0)의 최대 개수를 구해야 하는 문제다.

2.접근방법[알고리즘]

1.추가로 벽(1)을 세개 설치해야한다.

2.벽을 세개 설치 한 뒤 바이러스가 퍼진 결과를 구한다.

3. 그 결과에서 0의 개수를 구해준다.

4. 0의 개수를 저장해주며 벽을 다르게 설치할 때마다 0의 개수를 구하고 최댓값을 출력한다.

이렇게 풀기 위해서

벽을 세개 설치 하는 걸 DFS함수로 구현했다.

벽을 세개 설치하면 그 때 바이러스를 퍼트린 후 0의 갯수를 리턴한다.

DFS를 돌면서 ans변수에 최댓값을 저장해준다.

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;
				}
			}
		}
	}
}

2중 for문을 왜 저렇게 쓰는지 이해가 안가면

https://dingcoding.tistory.com/85

위 글의 3.문제풀이코드 부분에 설명을 보면 좋다.

벽을 설치한뒤 0의 갯수를 구하는 Count 함수를 구현했다.

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';
}

문제풀이후기

다중 for문을 사용해 벽을 세우는 방법도 있다.

그래도 위 코드처럼 DFS를 이용해서 벽을 세우고 백트래킹해주면

더 간결한 것 같다.