백준 15686번 치킨배달(C++)

문제

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

정답 코드

#include <iostream>
#include <algorithm>
int mapp[51][51];//지도
int valid[51][51];//치킨집 사용가능여부
int n,m;

using namespace std;

int min_point=21474836;

int	find_min(int y,int x)
{
	int len = 0;
	int min = 21474836;
	for (int i=1;i <= n; i++)
	{
		for (int j=1;j <=n; j++)
		{
			if (valid[i][j] == 1)
			{
				len = abs(x - j) + abs(y - i);
				if(len < min)
					min = len;
			}
		}
	}
	return (min);
}

void	cal_point()
{
	int	min =0;
	for (int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if (mapp[i][j] == 1)
				min += find_min(i,j);
		}
	}
	if (min < min_point)
		min_point = min;
}

void	valid_recur(int depth, int i,int j)
{
	if (depth == m)
		cal_point();
	if (i == n + 1)
		return ;
	for (int ti=i;ti <=n;ti++)
	{
		for (int tj=0;tj<=n;tj++)
		{
			if (i == ti && tj == 0)
				tj = j;
			if (mapp[ti][tj] == 2)
			{
				valid[ti][tj] = 1;
				if (tj == n)
					valid_recur(depth+1,ti+1,0);
				else
					valid_recur(depth+1,ti,tj + 1);
				valid[ti][tj] = 0;
			}
		}
	}
}
int main()
{
	cin >> n>>m;

	for (int i=1;i <=n;i++)
	{
		for (int j=1;j <=n;j++)
		{
			cin >> mapp[i][j];
		}
	valid_recur(0,0,0);
	cout<< min_point;
}

문제 풀이의 흐름

일단 이 문제를 풀 때 생각이 너무 꼬여서 순서도를 그렸다.

단순하게 생각하면

입력 받기

이용가능한 치킨집 고르기→ 모든 집에 대해서 최소 거리 점수 구하기 →다시 다른 치킨집 → 점수 구하기 이런식으로 모든 치킨집 경우에 대해서 문제를 해결하면 된다.

주의 할 점

나는 재귀를 탈 때 for문에서 if (i == ti && tj == 0) tj = j; 이걸 생각 안해주고 바로 j로 초기화 했다가 한참동안 헤맸었다.

그리고 처음에는 당연히 bfs로 풀려고 했는데 필요가 없었다.

반성 및 고찰

나는 모든 배열을 다 순회하지만 친구와 코드를 비교했을 때 친구는 치킨집의 위치와 집의 위치만을 배열에 담아서 해결했었다.

그게 훨씬 시간 복잡도도 빠르고 좋은 접근인 것 같다.

그리고 뭐가 틀렸는지 코드를 천천히 뜯어봐야 하고 어디서 틀릴수 있는지 가능성을 봐야 하는데 쓸 때 없이 계속 찍기만 해서 문제를 푸는데 긴 시간이 걸렸다.

오랜만에 알고리즘을 풀어서 오래 걸렸지만 다시 열심히 차근차근 해나갈 것이다.

Uploaded by N2T