BFS [BOJ14466] 소가 길을 건너간 이유 6

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

약 한달만에 풀이하는 문제라 그런지 굉장히굉장히 어려웠다.
사실 일반적인 BFS 문제이므로 문제 자체를 이해하는 것만 된다면 크게 어려울 것이 없었다.
하지만 c++이라는 언어의 변화, IDE 사용법 변화가 워낙 적응이 안되는 점이 컸다.

📌 첫번째 풀이

# include <iostream>
# include <queue>
# include <vector>
# include <cstring>

using namespace std;

int N, K, R, cnt;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };


struct XY {
	int x;
	int y;

	XY(int x, int y) : x(x), y(y) {};
};

queue<XY> que;
vector<XY> mat[101][101][4];
bool visited[101][101];
vector<XY> cows;


void bfs(XY first, XY sec) {
	que = queue<XY>();
	que.push(first);
	while (!que.empty()) {
		memset(visited, 0, sizeof(visited)); // visited 초기화
		XY xy = que.front();
		if (xy.x == sec.x && xy.y == sec.y)
		{
			cnt--;
			//cout << "first : " << first.x << first.y << " " << "second : " << sec.x << sec.y;
			break;
		}

		que.pop();
		for (int i = 0; i < 4; i++)
		{
			int newX = xy.x + dx[i];
			int newY = xy.y + dy[i];

			if (newX<1 || newX > N || newY<1 || newY > N || visited[newX][newY]) continue;
			bool road = false;
			for (int i = 0; i < mat[xy.x][xy.y].size(); i++)
			{
				if (mat[xy.x][xy.y][i].x == newX && mat[xy.x][xy.y][i].y == newY) {
					road = true;
					break;
				}
			}
			if (road) continue;
			que.push(XY(newX, newY));
			visited[newX][newY] = true;
		}
	}
}

void combi() {
	for (int i = 0; i < K; i++)
	{
		for (int j = i + 1; j < K; j++) {
			bfs(cows[i], cows[j]);
		}
	}
}

int main() {
	cin >> N >> K >> R;
	cnt = K * (K - 1) / 2;
	for (int i = 0; i < R; i++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		mat[x1][y1][].push_back(XY(x2, y2));
		mat[x2][y2].push_back(XY(x1, y1));
	}
	for (int i = 0; i < K; i++)
	{
		int x1, y1;
		cin >> x1 >> y1;
		cows.push_back(XY(x1, y1));
	}
	combi();
	cout << cnt;
}

시간 초과가 났다.
사실 케이스의 크기가 크지 않아서 별달리 고려하지 않고 bfs를 돌리면 될 것이라고 생각했는데,
길이 되는지 안되는지 판단 여부를
리스트를 순회하면서 찾다보니 시간복잡도가 많이 올라갔다.

📌 두번째 풀이

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int n, k, R;
int arr[101][101][4] = { 0, };
bool visited[101][101];
int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };

vector <pair<int, int>> cow;
int result = 0;
void bfs(int sy, int sx) {

	queue <pair<int, int >> que;
	que.push(make_pair(sy, sx));
	visited[sy][sx] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			if (arr[cy][cx][i] == 1) continue;
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny <1 || ny > n || nx < 1 || nx > n || visited[ny][nx] == 1)
				continue;
			que.push(make_pair(ny, nx));
			visited[ny][nx] = 1;
		}



	}


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

	cin >> n >> k >> R;

	int r, c, rr, cc;
	for (int i = 0; i < R; i++) {
		cin >> r >> c >> rr >> cc;
		for (int j = 0; j < 4; j++) {
			int nr = r + y_ar[j];
			int nc = c + x_ar[j];
			if (nr == rr && nc == cc) {
				arr[r][c][j] = 1; // 다리 생성
				arr[rr][cc][(j + 2) % 4] = 1;
			}
		}
	}

	for (int i = 0; i < k; i++) {
		cin >> r >> c;
		cow.push_back(make_pair(r, c));
	}

	for (int i = 0; i < k; i++) {
		memset(visited, 0, sizeof(visited));
		bfs(cow[i].first, cow[i].second);

		for (int j = i + 1; j < k; j++) {
			// bfs 돌림
			if (visited[cow[j].first][cow[j].second] == 0)
				result++;
		}
	}


	cout << result << endl;
	return 0;
}

사실 위 풀이는
https://gusdnr69.tistory.com/274
어떤 분의 코드를 참고하였다.
놀라운 점은 어느 한지점에서 다른 지점까지 판별하는 BFS를 돌리는 것이 아니라
한 지점에서 BFS를 돌려 갈 수 있는 모든 지점을 표시한다음, 출발지를 제외한 모든 지점들을 갈 수 있는지 체크했다는 것이다.

또한 다리도 나처럼 리스트로 2차원 배열에 넣는 것이 아닌,
배열을 3차원으로 만들어서 방향을 기준으로 길을 저장해놨다는 점이다.

배울점이 많은 문제였다..

📌 ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

이를 main에 쓰는 이유는 실행 속도를 빠르게 하기 위함이다.
정확한 이유는 reference 참고
https://jaimemin.tistory.com/1521

📌 배열 초기화

memset(visited, 0, sizeof(visited));

0(false)으로 visited 배열을 초기화하는 코드이다. 이를 사용하기 위해서는

#include <cstring>

위 헤더를 꼭 넣어주어야 한다.