[백준/BOJ] 백준 2842번 : 집배원 한상덕

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

2842번: 집배원 한상덕

투 포인터 알고리즘을 사용하여서 문제를 해결했다. 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <cstring>
using namespace std;

int n;
vector<string> board;
int height[50][50];
int visited[50][50];
int dxdy[8][2] = { {0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1} };

//here위치에서 갈수 있는 높이가 min_h 이상 max_h 이하일때 갈 수 있는 집의 개수를 구한다
int Solve(pair<int,int> here,int min_h, int max_h)
{
	visited[here.first][here.second] = 1;
	
	int ret = 0;

	//here가 집 위치일때
	if (board[here.first][here.second] == 'K')
		ret++;
	
	for (int i = 0; i < 8; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && min_h <= height[there.first][there.second] && max_h >= height[there.first][there.second] && visited[there.first][there.second] == 0)
		{
			ret += Solve(there, min_h, max_h);
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string input_s;
	int input_i;
	pair<int, int> post;
	int home_num = 0;
	vector<int> height_list;
	int result = 987654321;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> input_s;
		board.push_back(input_s);

		for (int j = 0; j < n; j++)
		{
			//우체국의 위치 저장
			if (input_s[j] == 'P')
				post = make_pair(i, j);

			//집의 개수를 센다
			else if (input_s[j] == 'K')
				home_num++;
		}
	}

	for(int i=0; i<n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> input_i;
			height[i][j] = input_i;
			height_list.push_back(input_i);
		}

	sort(height_list.begin(), height_list.end());
	height_list.erase(unique(height_list.begin(), height_list.end()), height_list.end()); //중복된 수를 지운다

	//투 포인터 알고리즘을 사용하였다
	int start_pointer = 0;
	int end_pointer = 0;
	while (1)
	{
		if (end_pointer == height_list.size())
			break;

		memset(visited, 0, sizeof(visited));

		//height_list[start_pointer]~height_list[end_pointer] 범위(높이 범위)안에서 모든 집에 우편 배달을 할 수 있을때
		if ((height[post.first][post.second] >= height_list[start_pointer] && height[post.first][post.second] <= height_list[end_pointer]) && Solve(post, height_list[start_pointer], height_list[end_pointer]) == home_num)
		{
			result = min(result, height_list[end_pointer] - height_list[start_pointer]);
			start_pointer++; //범위를 줄인다
		}

		else
			end_pointer++; //범위를 늘린다
	}	

	cout << result;

	return 0;
}