제2회 곰곰컵 풀이

A - 치킨댄스를 추는 곰곰이를 본 임스 2 풀이
B - 붙임성 좋은 총총이 풀이
C - 곰곰이와 학식 풀이
D - 오락실에 간 총총이 풀이
E - 곰곰이와 시소 풀이
F - 외로운 곰곰이는 친구가 있어요 풀이
G - 곰곰이와 테트리스 풀이
H - 곰곰아 선 넘지마 풀이
I - 곰곰이의 식단 관리 2 풀이
J - 서커스 나이트 풀이

BOJ 26071 - 오락실에 간 총총이 링크
(2022.12.01 기준 S2)

문제

N * N 크기의 칸으로 나누어져 있는 게임의 화면이 있고, 각 칸에는 곰곰이가 있거나 비어있다. 그리고 최소 한 마리의 곰곰이가 존재한다.
모든 곰곰이를 상하좌우 원하는 방향으로 한 칸씩 움직일 수 있고 화면 끝에 있는 곰곰이는 움직이지 않는다고 할 때, 모든 곰곰이들을 하나의 칸으로 모으는 최소 횟수 출력

알고리즘

N이 최대 1500개 이다. 일반적인 시뮬레이션을 돌리면 터지기 마련이므로, 각 방향에 대한 최소 횟수를 바로 구할 수 있어야 한다.

풀이

문제 예제를 보자.
만약 왼쪽으로 2번 밑으로 2번 누르면, 구석으로 전부 몰 수 있다.
오른쪽으로 2번 위로 2번 누르면? 그래도 구석으로 전부 몰 수 있다.
하지만 절대 맨 끝 라인이 아닌 곳으로 몰 수 없다.
그런데 이런 모양이라면? 왼쪽이나 오른쪽으로 2번 누르면 된다. 상하를 기준으로 맨 끝 라인이 아닌 곳으로 몰지 않아도 된다. 행이나 열 기준으로 한 줄에 전부 곰곰이가 있다면, 수직인 방향으로 움직이지 않아도 된다는 말이다.
이런 모양이라면? 왼쪽으론 2번, 오른쪽으로 1번만 누르면 된다.
결국 요약하자면,
행이나 열 기준으로 최소 최대 위치를 구하자. 최소와 최대가 같지 않다면, min(최소 위치에서 N - 1 위치까지 누르는 횟수, 최대 위치에서 0 위치까지 누른 횟수)를 눌러야 하는 것이다. 이를 행과 열마다 각각 구해주면 된다.

코드

import sys; input = sys.stdin.readline

N = int(input())
matrix = [input().strip() for _ in range(N)]

li = lj = N # i, j의 최소
ui = uj = -1 # i, j의 최대

# 곰곰이가 나올 때마다 최소와 최대를 갱신한다.
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 'G':
            if li > i:
                li = i
            if ui < i:
                ui = i
            if lj > j:
                lj = j
            if uj < j:
                uj = j

# 곰곰이가 한 줄에 있으면. 즉, 최대와 최소가 같다면 그 수직 방향으론 움직일 필요가 없는 것이다.
# 아니면, 맨 끝으로 몰아야 할 수 밖에 없다.
# 최대 위치에서 0으로 몰던지 최소 위치에서 N - 1로 몰던지 해야 한다.

answer = 0
if li != ui:
    answer += min(ui, N - 1 - li)
if lj != uj:
    answer += min(uj, N - 1 - lj)
print(answer)