[C++/백준] 16724 피리 부는 사나이

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

16724번: 피리 부는 사나이

 

 

[ 아이디어 구상 ]

일단 처음에 문제를 읽고 시뮬레이션이라고 생각했다. 

 

말을 좀 어렵게 써놨는데 예시 그림?을 보면서 생각해보면 결국 구하는 것이 말이 'SAFE ZONE'이지 연결되지 않은 땅의 개수인 걸 알 수 있었다.

 

구하는 것 : 연결되지 않은 땅 개수

=> BFS 아님 DFS로 구하면 되겠구나를 알 수 있었다. 

 

그리고 방향으로 생각해 보면 연결되는 건 두 가지 인데,

1) 내가 서 있는 땅에서 가야하는 방향 

2) 나한테 들어오는 방향의 땅

이 두가지를 고려해주면 된다. 

 

1의 경우 쉬운데 2는 그럼 어떻게 알 수 있을까??????

내가 서 있는 땅으로 들어오는 방향의 땅들을 탐색할 때, 항상 그렇듯 4방향 배열로 구해줄 거라고 생각하면 

 

초록색 : 내가 탐색하는 dy[] = {1, -1, 0, 0} dx[] = {0, 0, -1, 1}

검은색 : 나한테 들어오는 경우의 방향 인데 

 

내가 있는 좌표를 (2,2) 라고 뒀을 때,

위쪽 좌표(1,2)의 방향을 확인했을 때 dy[i] = -1, dx[i] = 0 이 되고 

그 방향에서 내가 있는 좌표와 연결되기 위해 적혀있어야 할 방향은 D(1,0)이다. 

 

즉 서로 x -1을 해서 같아지는 방향이라는 것이다 ㅇㅇ .

 

이걸 떠올린 다음 손 코딩을 들어갔다. 기본적인 BFS를 사용하면 되는데 

1) 내가 가야하는 다음 좌표

2) 나한테 들어오는 좌표

 

두 가지 경우 모두 고려해서 짜줬다. 

그리고 입력이 UDLR 처럼 문자로 들어와서 그냥 if문을 써도 금방 될 거 같긴 하지만,,,

map 자료형을 써서 편하게 하기로 했다.

 

[ 문제 풀이 ]

#include<iostream>
#include<string>
#include<queue>
#include<map>

using namespace std;

int N, M;
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,-1,1 };
vector<string> board;
vector<vector<int>> visited;
map<char, pair<int, int>> m; // UDLR 검색.

void BFS(int y, int x){
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = 1;

	while (!q.empty()) {
		
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		
        // 내가 가야하는 좌표는 넣음
		int gy = y+m[board[y][x]].first;
		int gx = x+m[board[y][x]].second;
		if (!visited[gy][gx]) {
			visited[gy][gx] = 1;
			q.push({ gy,gx });
		}
		
        // 나한테 들어오는 방향의 좌표 넣음
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (visited[ny][nx]) continue;
            // 탐색한 방향의 반대가 되는 경우 넣음
			if (m[board[ny][nx]].first == -1 * dy[i] && m[board[ny][nx]].second == -1 * dx[i]) {
				q.push({ ny,nx });
				visited[ny][nx] = 1;
			}
		}
	}
}

int main() {
	cin >> N >> M;
	cin.ignore();
	m['U'] = { -1,0 };
	m['D'] = { 1,0 };
	m['L'] = { 0,-1 };
	m['R'] = { 0,1 };
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		board.push_back(s);
		vector<int> v(M);
		
		fill(v.begin(), v.end(), 0);
		
		visited.push_back(v);
	}
	int ans = 0;


	for (int y = 0; y < N;y++) {
		for (int x = 0; x < M; x++) {
			if (visited[y][x]) continue;
			BFS(y, x);
			ans += 1;
			
		}
	}

	std::cout << ans;

}

 

 

++ 

다른 포스팅을 좀 찾아보니까 DFS로 많이 푸는 것 같다. 

이게 (밖으로 나가는 경우가 없다) 라는 조건에 의해서 무조건 사이클이 생기고 그렇게 되면 그 사이클 개수를 찾으면 된다고 함..!! visted[y][x] = 1이 되는 경우에 사이클이 생긴다고 보고 종료하는 방법인 것 같다 

 

 

[고찰]

풀면서 실수가 좀 많았따... 손코딩 + 1차 코딩까지 30분? 정도가 걸렸는데 잔실수에,,,

아직도 언어에 안 익숙한지 헷갈리는 게 많아서 시간도 오래걸리고 디버깅도 계속 해줬다. 

 

일단... 방향을 잘못 생각해줘서 한번 틀렸었다. U = -1,0 인데 뇌빼고 사는 듯 1,0으로 해줘서 으휴 ㅋㅋ 코딩 접어라

 

두번째로 입력할 때 뻘짓하다가 틀렸는데.. 여기서 진짜 뭐 떄문에 틀린지도 모르겠어서 결국 chatGPT를 사용했다. 

입력이 제대로 안되면..ㅠㅠ

 

문자열이라고 또 getline으로 뻘짓하다가 오류가 생긴거 였는데.. 사실 공백이 없어서 그냥 cin으로 받으면 됨 

for 문 안에 cin.ignore()랑 getline을 순차적으로 써서 생긴 오류였다. 

 

이게 ignore가 단순히 개행문자 포함인 줄 알았는데 위 사진처럼 3을 입력 받은 후 cin.ignore(4)를 하면 그 뒤에 들어오는 것까지 다 지워진다고 한다. 

그래서 내가 받은 입력에 첫번째 문자가 계속 지워졌고 ㅠㅠ ...

 

잘하자..

 

추가로 int 배열 범위가 계속 헷갈리기도 하고 잘 모르겠는데 한 백만까지는 버티는 듯