백준 9205번 맥주 마시면서 걸어가기 C++ BFS, 넓이 우선 탐색

리뷰

 

시작 지점과 편의점과 도착지점을 같은 배열을 통해 사용했는데 배열의 크기를 편의점의 개수로만 초기화 해서 틀려버렸다 ㅠㅠ

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

 

문제 풀이

1. 전역 변수로 테케개수용 tc, 편의점 개수 n, 총 노드의 개수 length를 초기화 해주었다.
2. 방문 배열 및 인접 리스트용 Pos 구조체 타입의 벡터 path와 정답을 저장할 문자열 타입 벡터 ans를 전역 초기화
3. init 함수를 통해 각 테스트 케이스마다 인접 리스트와 방문 배열을 초기화 해주었다.
4. input 함수를 통해 n값과 path 벡터에 시작지점, 편의점, 도착정보를 입력 받아 인접리스트를 생성해 준다.
5. bfs 함수를 통해 각 인접리스트를 순회하며 탐색을 하고, 도착지점에 도착을 하면 true를 리턴해 준다.
6. 만약 큐가 빌때까지 도착 지점에 도달하지 못한다면 false를 리턴해 준다.
7. bfs 결과가 참일 경우 happy를 ans벡터에 추가, 거짓일 경우 sad를 ans벡터에 추가해 준다.
8. 모든 테케가 종료된 후 ans에 저장되어 있는 값을 출력해 준다.

 

참고 사항

시작과 도착지 정보를 다른 변수로 저장한다면 상관 없지만, 나처럼 시작과 도착지 정보를 동일한 벡터로 관리할 거라면 방문배열의 값을 102개 이상으로 설정해 주어야 한다. (편의점의 최대 개수 100개 + 시작 지점 1개 + 도착지점 1개)

 

 

정답 코드

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

using namespace std;
int tc, n, length;
int v[103]; // 최대 편의점 개수

struct Pos {
	int x, y;
};
vector<Pos> path; // 인접 리스트
vector<string> ans;

void init() { // 초기화 함수
	path.clear();
	memset(v, 0, sizeof(v));
}

void input() { // 입력 받기
	cin >> n;
	for (int i = 0; i < n + 2; i++) { // 시작지점 + 편의점 + 도착지점
		int x, y; cin >> x >> y;
		path.push_back({ x, y });
	}
	length = n + 2;
}

int calc_dist(int x1, int y1, int x2, int y2) { // 거리 계산 함수
	return abs(x1 - x2) + abs(y1 - y2);
}

bool bfs() {
	queue<Pos> q;
	q.push({ path[0] }); // 시작 지점 큐에 추가
	v[0] = 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;

		for (int i = 0; i < length; i++) { // 인접리스트 탐색
			if (v[i]) continue;
			Pos next = path[i];
			int nx = next.x, ny = next.y;
			int dist = calc_dist(cx, cy, nx, ny);
			if (1000 >= dist) { // 현재 좌표에서 다음 좌표까지 갈 수 있는고?
				if (i == length - 1) return true; // 도착지점이면 리턴
				v[i] = 1;
				q.push({ nx, ny });
			}
		}
	}
	return false; // 도착지점까지 가지 못했음
}

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

	cin >> tc;
	while (tc--) {
		init();
		input();
		if (bfs()) ans.push_back("happy");
		else ans.push_back("sad");
	}
	for (string s : ans) cout << s << "\n";
}