[BAEKJOON] 16724. 피리 부는 사나이
Posted on
문제 :
피리 부는 사나이 성우는 오늘도 피리를 분다.
성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 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’의 최소 개수를 출력한다.
풀이 :
Disjoint Set을 이용하면 문제를 해결할 수 있을 것이라고 생각하고 접근했던 것 같다.
우선 safe zone 갯수 자체가 경로가 묶인 무리(clan) 갯수라고 봐도 무방했다. 따라서 disjoint set의 갯수를 센다면 그것이 답이라고 생각했다.
전형적인 Disjoint Set 구현 방식인 find, union 함수를 사용하지는 않았다. 각 칸의 CLAN 번호를 저장하여 자신보다 낮은 번호에 방문했을 경우 해당 무리의 번호를 모두 낮은 번호로 바꿔주는 방식을 사용했다.
결론적으로 서로소 집합 갯수를 세는 방식이긴 하나 Disjoint set 구현 방식이 익숙치 않은 탓에 더 빨리 구현할 수 있는 방법을 두고 돌아간 느낌이었다. dijoint set 구현 연습을 좀 진행할 예정이다.
코드 :
코드 보기/접기
#include <iostream>
#include <cstring>
#define MAX 1000
using namespace std;
int board[MAX][MAX], clan[MAX][MAX], cnt, di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0}, n, m;
int searchClan(int x, int y) {
int cmpx = x + di[board[x][y]], cmpy = y + dj[board[x][y]];
clan[x][y] = cnt;
if (clan[x][y] == clan[cmpx][cmpy] || cmpx < 0 || n <= cmpx || cmpy < 0 || m <= cmpy) return clan[x][y];
else if (clan[cmpx][cmpy] == -1) return clan[x][y] = searchClan(cmpx, cmpy);
else return clan[x][y] = clan[cmpx][cmpy];
}
int main() {
int i, j;
char input;
cin >> n >> m;
memset(clan, -1, sizeof(clan));
for (i = 0; i < n; i++)
for (j = 0; j < m; j++) {
cin >> input;
switch (input) {
case 'R':
board[i][j] = 0;
break;
case 'D':
board[i][j] = 1;
break;
case 'L':
board[i][j] = 2;
break;
case 'U':
board[i][j] = 3;
break;
}
}
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (clan[i][j] == -1)
if (cnt == searchClan(i, j)) cnt++;
cout << cnt << '\n';
return 0;
}