백준 26124번 조명 배치

문제 설명

이번 문제는 격자 칸에 조명을 배치할 경우 아래와 같은 규칙으로 각 격자칸의 영향력이 정해질 경우, 각 칸의 영향력이 정해진 격자칸이 주어졌을 때 필요한 조명의 최소 개수를 구하는 문제입니다. (해당 격자칸으로 조명 배치를 만들 수 없을 경우 -1 출력)

 

조명 L의 밝기가 c일 경우 L이 각 빈칸에 미치는 영향력은 다음과 같이 계산된다.

• L이 위치한 격자칸에 미치는 영향력은 c이다.
• L과의 거리가 1인 격자칸에 미치는 영향력은 c-1이다.
•  …
•  L과의 거리가 c-2인 격자칸에 미치는 영향력은 2이다.
•  L과의 거리가 c-1인 격자칸에 미치는 영향력은 1이다.
• 그 외의 빈칸에는 영향력을 미치지 않는다.

어떤 빈칸에 영향을 미치는 조명의 개수가 2개 이상인 경우, 이 빈칸의 영향력은 영향을 미치는 조명의 영향력의 최댓값입니다.

 

 

문제 풀이

아이디어

규칙을 만족하지 못하는 경우

각 격자칸의 상하좌우에 있는 격자칸은 거리가 1이므로 영향력은 1차이가 나야됩니다.

영향력이 1 크다면 해당 격자가 더 조명에 가까운 것이고, 영향력이 1 작다면 해당 격자가 더 조명에서 멀다고 생각하면 됩니다.

 

그러므로, 영향력의 차이가 2 이상 나는 경우 문제의 조건에 부합하지 않으므로 해당 격자칸으로 조명배치를 만들 수 없습니다.

 

규칙을 만족하는 경우

위와 같이 붙어있는 격자칸의 영향력 차이가 2이상 나는 경우를 제외한다면 어떤한 경우에도 조명 배치를 만들 수 있습니다.

 

그 이유는,

만약 왼쪽 격자의 영향력이 3 오른쪽 격자의 영향력을 4라고 한다면, 왼쪽 격자보다 오른쪽 격자가 조명에 더 가까운 경우라고 할 수 있습니다.

만약 왼쪽 격자의 영향력이 3 오른쪽 격자의 영향력을 3이라고 한다면, 왼쪽 격자와 오른쪽 격자는 각자의 조명에 의해 영향을 받고 있거나, 왼쪽 오른쪽 격자에 조명이 있어 각자에 영향력을 주지 않는 경우라고 할 수 있습니다.

 

문제에서 주어진 것은 조명에서 거리가 1 늘어날수록 영향력이 1 줄어든다는 것입니다.

문제에서 구하고자 하는 것은 필요한 조명의 최소 개수이므로, 격자의 빛 영향력에 따라 최소한으로 조명의 개수를 늘려 해당 격자의 조명 배치를 만족하는 조명의 최소 개수를 구하면 됩니다.

 

풀이

조명의 개수

각 격자의 영향력을 내림차순으로 정렬한뒤 해당 격자를 방문하지 않았다면 반복문을 실행합니다.

 

방문하지 않은 격자일 경우 해당 격자에 조명을 배치합니다.

{해당 격자의 영향력 - 다음 격자의 영향력}이 1일 경우 현재 조명의 영향을 받고 있는 경우이므로 다음 격자를 queue에 넣는 것을 반복합니다.

 

만약 이 때 {해당 격자의 영향력 - 다음 격자의 영향력}가 2이상일 경우 조건을 만족하는 조명 배치를 만족할 수 없으므로 -1을 출력하고 종료합니다.

 

반복문의 끝까지 {해당 격자의 영향력 - 다음 격자의 영향력}가 2이상인 경우가 없다면 조건을 만족하는 조명 배치를 만들 수 있다는 것이므로 현재까지 배치한 조명의 개수를 출력해줍니다.

 

 

 

해결

규칙을 만족하지 않을 경우에 대한 처리가 제대로 되지 않아 오래 걸렸던 문제입니다...

 

문제 링크 : https://www.acmicpc.net/problem/26124

26124번: 조명 배치

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/26124.py