[BOJ] 16724 피리 부는 사나이

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

16724번: 피리 부는 사나이

문제

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다. 

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.

지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

입력	출력
3 4 DLLL DRLU RRRU	2

---

한번 움직일 때 4가지 방향 중에 한 방향으로 밖에 움직이지 못하기 때문에 

자식 노드가 1개씩인 트리를 여러개 순회하는 것과 같다고 생각할 수 있다.

따라서 방문했는지 표시해가면서 배열의 모든 좌표를 방문하는 경우에

DFS가 호출되는 횟수가 정답이라고 생각해서 문제를 풀었는데

틀렸습니다를 받았다.

 

반례가 뭐가 있을까하고 생각해보니

DFS 경로가 달팽이처럼 되어 있고 재수 없이 중간부터 DFS를 하는 경우엔

SAFE ZONE이 하나가 아니라 여러개 나올 수 도 있겠다는 생각이 들었다.

이런 경우를 처리하려면 집합을 나타내줄 수 있는 union-find를 적용해야지 싶어서

조금 구현해봤는데 2차원 배열로 이걸 적용하려니 쉽지 않았다. 

좀 더 생각해보니 DFS랑 union-find를 둘 다 적용할 필요가 없었다.

 

visit 배열을 사용해서 문제를 풀었다.

값이 0인 경우엔 아직 방문하지 않음

1인 경우엔 사이클을 찾는 중

2인 경우엔 사이클이 완성됨을 나타낸다.

따라서 DFS 중에는 visit 배열을 1로 유지하다가 DFS가 끝나면 2로 만든다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>

int N, M;
char map[1001][1001];
int visit[1001][1001];
int zone;
int next_x[4] = { -1, 1, 0, 0 };
int next_y[4] = { 0, 0, -1, 1 };

void DFS(int x, int y) {
	int dir;
	visit[x][y] = 1;

	switch (map[x][y]) {
	case 'U': dir = 0; break;
	case 'D': dir = 1; break;
	case 'L': dir = 2; break;
	case 'R': dir = 3; break;
	}

	int nx = x + next_x[dir];
	int ny = y + next_y[dir];

	if (visit[nx][ny] == 1) zone++;
	else if (visit[nx][ny] == 0) DFS(nx, ny);
	visit[x][y] = 2;

}

int main() {
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= M; j++) {
			scanf("%c", &map[i][j]);
		}
	}

	memset(visit, 0, sizeof(visit));

	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++) {
 			if (visit[i][j] == 0) {
				DFS(i, j);
			}
		}
	}

	std::cout << zone;

	return 0;
}

 

후기)

다른 블로그를 보니 set을 사용하는 경우도 있었다.

매번 내가 C++을 쓰고 있는지 까먹어서 힘든 길을 간다...

시작할 때는 만만해보였는데 풀다보니 그리 만만하지 않더라.

역시 세상엔 만만한 일이 없다.

 

바른치킨 스파이크 치킨? 별로 맛없다.