Kcode

www.acmicpc.net/problem/15686

생각보다 쉽게 풀었다. 치킨집이 총 13개까지 주어지는 조건을 봤고,

치킨집과 집을 매칭 시키는 것이 combination을 떠올리게 한다.

따라서 그래프 탐색이 아니라 조합, 경우의 수로 접근해봤다.

일단 보자마자 집을 원소로 가지는 a벡터, 치킨집을 원소로 가지는 b벡터를 인자로

받아 각 원소를 \(O(N^2)\)으로 순회하며 가장 작은 치킨 거리를 찾아 리턴해주는 함수를 만들었다.

이건 쉽게 구현 가능하고 이제 치킨집에서 총 M개의 원소를 뽑아서 각각 a, b를 매칭 시켜주면 된다.

처음에는 next_permutation을 이용한 순열로 접근했지만 모든 경우의 수를 따지면 시간초과가 난다.

그래서 지우고 조합으로 다시 접근해줬는데 n과m 문제를 풀어봤다면 쉽게 구현 가능하다.

www.acmicpc.net/problem/3190

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

deque를 사용하면 앞뒤로 삽입과 삭제를 용이하게 할 수 있다.

일단 방향을 정해주는데 북, 동, 서, 남을 차례로 0, 1, 2, 3으로 설정해준다.

이러면 dx, dy해주는 부분은

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

가 되고, 방향을 조절해주는 함수는 다음과 같이 쉽게 작성할 수 있다.

void dir(char C) {
	if (C == 'L') !d ? d = 3 : d--;
	else d == 3 ? d = 0 : d++;
}

처음에는 X와 C가 주어지면 X만큼 이동 후 C방향으로 회전시키는 것인 줄 알았는데

X가 현재 초를 가르키는 거라 고생 좀 했다.

우선 뱀이 움직이는 부분은 쉽게 구현 가능하다.

아무것도 아닌 부분은 '.', 뱀이 위치하고 있는 부분은 'o', 사과가 존재하는 부분은 '*'로 놓고

위처럼 구현하고 dir함수를 통해 방향을 바꿔준다.

이제 남은 구현부분은 이미 충돌했거나, 범위 밖을 벗어나는 경우 더 이상 X와 C를 받지 않고

빠져나와야 하는데 나는 뱀이 이동하는 bfs 함수를 boolean으로 작성하여 해결했다.

만약 중간에 반복문을 빠져나온게 아니라 query를 전부 수행했다면

이제 벽에 박을 때까지 진행시켜주면 된다.

최종 코드

www.acmicpc.net/problem/1446

문제는 그리디 하게 접근해야 한다는 것이다. 그냥 지름길이 주어졌다고 해서 지금 길만 탄다면

다른 컴포넌트에 있는 길로 가는 것이 더 빠를 수 있다.

어떻게 접근해야 할까?

핵심은 다익스트라를 돌리면서 현재 위치 + 1 에 지름길이 없다면 우선순위 큐에 

cost + 1 로 넣어주는 것이다.

이렇게 되면 자연히 d 이하의 모든 노드를 탐색하면서 지름길이 있다면 지름길을 타고, 아니라면

다음 컴포넌트가 큐에 들어가게 된다.

k 가 고속도로의 길이 d라고 하면 현재 위치 cur + 1 이 k보다 작아야 하고(고속도로를 역주행할 수는 없기 때문에)

그다음 위치가 현 비용 + 1 보다 크다면(INF라면) 

다른 컴포넌트이기 때문에 그 위치를 큐에 넣어줘야 한다.