💡문제
우연히 들리게 된 오락실에서, 총총이는 귀여운 곰곰이가 잔뜩 등장하는 게임을 발견했다.
게임의 화면은
크기의 칸으로 나누어져 있고, 각 칸에는 곰곰이가 있거나 또는 비어있다. 화면에는 최소 한 마리의 곰곰이가 존재한다.
게임은 상하좌우 네 개의 버튼을 눌러서 진행할 수 있다. 각 버튼을 누르게 되면, 화면에 있는 모든 곰곰이들이 그 버튼에 해당하는 방향으로 한 칸 움직이게 된다. 만약 이미 화면의 끝에 있어서 그 방향으로 이동하지 못하는 곰곰이들은 가만히 있는다. 버튼을 잘 눌러서 모든 곰곰이들을 하나의 칸에 모으게 되면, 화면에 GOMGOM 이라는 글자가 뜨면서 승리하게 된다.
현재 오락실에서는 이 게임을 가장 적은 횟수의 버튼을 눌러서 승리한 플레이어에게 곰곰 피규어를 주는 이벤트를 진행하고 있다. 귀여운 곰곰 피규어를 노리는 총총이를 위해, 최소 몇 번의 버튼을 눌러야 게임을 클리어할 수 있는지를 구해보자.
입력
첫째 줄에 정수 이 주어진다.
둘째 줄부터 개의 줄에 걸쳐 게임 화면의 상태가 주어진다. 각 줄에는 개의 문자가 공백없이 주어지고, 모든 문자는 또는 중 하나이다. 는 그 칸에 곰곰이가 있다는 뜻이고, 는 그 칸이 비어있음을 의미한다.
최소 하나 이상의 문자가 주어짐이 보장된다.
출력
모든 곰곰이를 하나의 칸에 모으기 위해, 총총이가 최소 몇 번 버튼을 눌러야 하는지 구하시오.
예제입력
3
.G.
G.G
.G.예제출력
4📖내가 실패한 Code
import sys
sys.setrecursionlimit(10**9)
"""
n*n 칸 최소 1개의 곰곰이 각 버튼 누르면 모든 곰곰이들 이동. 화면 끝에 있는 애들은 가만히
걍 한 곳에 몰면 안되나?
"""
def find_max_gps(n, array):
len_array = len(array)
if len_array == 1:
return 0
if all(array[0][0] == array[i][0] for i in range(1, len_array)):
array.sort(key=lambda x: x[1])
return min(array[-1][1] + array[0][1], abs(array[-1][1] - n) + abs(array[0][1] - n))
elif all(array[0][1] == array[i][1] for i in range(1, len_array)):
array.sort(key=lambda x: x[0])
return min(array[-1][0]+array[0][0], abs(array[-1][0] - n)+abs(array[0][0] - n))
result = 0
array.sort(key=lambda x: x[1])
result += min(array[-1][1] + array[0][1], abs(array[-1][1] - n) + abs(array[0][1] - n))
array.sort(key=lambda x: x[0])
result += min(array[-1][0] + array[0][0], abs(array[-1][0] - n) + abs(array[0][0] - n))
return result
def main():
inputs = sys.stdin.read().splitlines()
n = int(inputs[0])
gomgoms = [(i-1, j) for j in range(n) for i in range(1, n+1) if inputs[i][j] == 'G']
sys.stdout.write(str(find_max_gps(n-1, gomgoms)))
if __name__ == "__main__":
main()
📖내가 작성한 Code
import sys
"""
n*n 칸 최소 1개의 곰곰이 각 버튼 누르면 모든 곰곰이들 이동.
좌상,우상,좌하,우하 4가지 비교해야함
"""
def find_max_gps(max_idx, array):
hMin = min(r for r, c in array)
hMax = max(r for r, c in array)
vMin = min(c for r, c in array)
vMax = max(c for r, c in array)
if hMin == hMax and vMin == vMax:
return 0
if hMin == hMax:
return min(vMax, max_idx - vMin)
if vMin == vMax:
return min(hMax, max_idx - hMin)
return min(hMax + vMax, (max_idx - hMin) + (max_idx - vMin),
hMax + (max_idx - vMin), (max_idx - hMin) + vMax)
def main():
inputs = sys.stdin.read().splitlines()
n = int(inputs[0])
gomgoms = [(i-1, j) for j in range(n) for i in range(1, n+1) if inputs[i][j] == 'G']
sys.stdout.write(str(find_max_gps(n-1, gomgoms)))
if __name__ == "__main__":
main()
✍️풀이과정
처음에는 양 극단으로 몰면 되지 않을까? 해서 빠르게 작성하였지만, 반례가 많았던 문제. 먼저 1개일 경우, 2번째 같은 줄에 있을 때를 고려하지 않았다.
실랜디를 하는게 정답이었다. 실버도 이렇게 실수가 잦다.
이럴 때 일수록, 엣지케이스를 생각해야하는데, 먼저 행이나 열에 하나만 있는 경우, 전부 한줄에 몰려있는 경우, 전부 채워진 경우 등등을 고려해서 테스트케이스에 넣어보는 습관을 가져야겠다.
🧠 코드 리뷰
- 로직: 입력으로 주어진 n*n 격자에서 'G' 문자의 좌표들을 추출하여, 행과 열의 최소/최대값을 구한 뒤 버튼을 눌렀을 때 각 곰곰이가 이동할 수 있는 최소 거리를 계산하는 방식은 문제의 요구에 맞게 구현되었습니다.
각 경우(모든 곰곰이가 한 행 또는 한 열에 있는 경우와 그렇지 않은 경우)에 대해 이동 거리의 최솟값을 구하는 방식도 적절해 보입니다.
🛠️AI 개선 코드
import sys
def solution():
input = sys.stdin.readline
N = int(input())
# 초기값 설정: 최소값은 최대 N, 최대값은 0으로 시작
min_row, max_row = N, 0
min_col, max_col = N, 0
# 각 행마다 왼쪽과 오른쪽 'G'의 인덱스를 파악하여 min/max 업데이트
for i in range(N):
state = input().rstrip()
# state.lstrip('.')로 왼쪽의 '.'을 제거하면 제거된 문자의 수가 왼쪽 'G'의 인덱스가 됨
left_index = N - len(state.lstrip('.'))
# state.rstrip('.')로 오른쪽의 '.'을 제거하면 남은 문자열의 길이가 오른쪽 'G'의 인덱스+1
right_index = len(state.rstrip('.')) - 1
# 만약 해당 행에 'G'가 없으면 right_index가 -1이 됨
if right_index < 0:
continue
# 행의 최소/최대값 갱신
min_row = min(min_row, i)
max_row = max(max_row, i)
# 열의 최소/최대값 갱신
min_col = min(min_col, left_index)
max_col = max(max_col, right_index)
res = 0
# 만약 여러 행에 'G'가 존재하면, 위쪽과 아래쪽 이동 중 작은 값을 더함
if max_row > min_row:
res += min(N - min_row - 1, max_row)
# 만약 여러 열에 'G'가 존재하면, 좌측과 우측 이동 중 작은 값을 더함
if max_col > min_col:
res += min(N - min_col - 1, max_col)
print(res)
solution()
💻결과
🖱️참고 링크
