백준 15559번 내 선물을 받아줘

🔒[문제 url]

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

🔑알고리즘

한 지점에서 DFS를 진행하여 갈 수 있는 모든 지점에 같은 값으로 표기한다.
이후 다른 지점에서 DFS를 진행하여 형성된 구간이 이미 값이 표기되어 있는 지점을 만난다면, 해당 구간도 동일한 값으로 표기한다.
만나지 않고 탐색이 종료된다면, 다른 값으로 표기한다.표기를 마친 후 구역의 갯수가 출력 답안이 된다.

🐾부분 코드

int n,m;
string inp;
int map[1001][1001];

typedef pair<int,int> pii;
pii dir[4] = {{0,1},{0,-1},{1,0},{-1,0}};//E W S N
int visited[1001][1001];
int cnt = 1;

void INPUT()
{
	IAMFAST
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		cin >> inp;
		for (int j = 0; j < m; j++)
		{
			switch (inp[j])
			{
			case 'E' : map[i][j] = 0; break;
			case 'W' : map[i][j] = 1; break;
			case 'S' : map[i][j] = 2; break;
			case 'N' : map[i][j] = 3; break;
			}
		}
	}
}

<변수 선언 및 입력>
$E,W,S,N$를 각각 숫자로 변환해 지도에 나타낸다. 각 숫자는 dir 배열에서의 index를 나타내고, DFS 함수에서 방문 지점을 갱신한다.
cnt는 구역의 갯수이자 출력 답안이 된다.

int DFS(int x,int y)
{
	visited[x][y] = cnt;

	int nx = x+dir[map[x][y]].first;
	int ny = y+dir[map[x][y]].second;

	if(!visited[nx][ny])
		visited[x][y] = min(visited[nx][ny],DFS(nx,ny));
	else visited[x][y] = visited[nx][ny];
	
	return visited[x][y];
}

<DFS 함수>
다음에 방문할 지점이 이미 갱신되어있다면, 즉 이미 구역이 표기되어있다면 같은 값으로 표기한다.
표기되어있지 않다면, 방문할 지점에서 다시 DFS를 진행해 표기할 값을 정한다.

void SOLVE()
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(!visited[i][j])
				if(DFS(i,j) == cnt) cnt++;
	cout << cnt-1;
}

<DFS 반환값 통해 구역 갯수 갱신>
한 지점에서 DFS를 진행하여 형성된 구간이 이미 값이 표기되어 있는 지점을 만나지 못했다면 cnt를 1 더한다.
즉 독립된 구간이 하나씩 늘어날때마다 cnt는 1씩 증가하므로,
탐색 종료 후cnt-1이 답이 된다. 마지막 탐색에서 cnt++을 하며 탈출하므로 1을 빼준다.

🪄전체 코드

#include <iostream>
#include <string>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n,m;
string inp;
int map[1001][1001];

typedef pair<int,int> pii;
pii dir[4] = {{0,1},{0,-1},{1,0},{-1,0}};//E W S N
int visited[1001][1001];
int cnt = 1;

void INPUT()
{
	IAMFAST
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		cin >> inp;
		for (int j = 0; j < m; j++)
		{
			switch (inp[j])
			{
			case 'E' : map[i][j] = 0; break;
			case 'W' : map[i][j] = 1; break;
			case 'S' : map[i][j] = 2; break;
			case 'N' : map[i][j] = 3; break;
			}
		}
	}
}

int DFS(int x,int y)
{
	visited[x][y] = cnt;

	int nx = x+dir[map[x][y]].first;
	int ny = y+dir[map[x][y]].second;

	if(!visited[nx][ny])
		visited[x][y] = min(visited[nx][ny],DFS(nx,ny));
	else visited[x][y] = visited[nx][ny];
	
	return visited[x][y];
}

void SOLVE()
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(!visited[i][j])
				if(DFS(i,j) == cnt) cnt++;
	cout << cnt-1;
}

int main()
{
	INPUT();
	SOLVE();
}

🥇문제 후기

만만히 봤다가 생각보다 오래 걸린 문제이다.
현재 새벽 4시... 자세히 쓰기엔 너무 피곤해서 이하생략..ㅠㅠ