문제 출처 : 코드트리_2개의 사탕
티어 : 골드1
유형 : 시뮬레이션, BFS
출제 : 2015년 하반기 통합 2번
주의사항 : 중력구현과 사탕이 동시에 나가는 상황
삼성에서 1번에 브론즈 문제를 내고, 바로 출제한 골드1 난이도의 문제입니다. 1번을 풀고 싱글벙글 웃으며 2번 문제를 열어보았을 지원자들의 표정이 눈에 선합니다. 시키는대로 구현하면 되는 문제이지만, 섣불리 코드를 짜다가는 놓치는 케이스가 빈번하게 발생하는 문제입니다. 주의사항에 적은 두 가지가 대표적으로 많이 실수하는 부분이므로, 문제를 꼼꼼히 읽고 코드를 짜도록 합시다.
생각의 흐름
최대 10번 밖에 움직이지 않으며 최소 횟수를 출력하는 문제이기 때문에 백트래킹보다 디버깅이 용이한 큐를 사용하자고 다짐했습니다. 반복문이 끝날 때까지, 즉 큐가 텅 빌때까지 반복하며 빨간 사탕이 나올 때의 횟수를 기록하고 중단하면 되겠다고 마음을 먹었습니다. 그래프에서 이동하는 것은 파란 사탕과 빨간 사탕 뿐이므로 그래프에서 사탕들만 큐에 넣는 것이 그래프 전체를 넣는 것보다 메모리 절약에 도움이 되겠다고 생각해서 사탕의 좌표를 분리해 저장했습니다.
또한 중력을 구현할 때, 예를 들어 아래의 상황에서 오른쪽으로 기울인다고 했을 때,
아래와 같은 답이 나와야 하지만,
일반적으로 벽을 만났을 때 멈추게 한다면 사탕이 겹치게 되거나,
겹치지 않도록 하면 서로가 서로를 인식하게 되거나,
그렇다고 해서 다른 사탕을 만나면 멈추도록 중력을 구현하면 뒤쪽에 있던 구슬이 중간에 막히는 일이 발생할거라는
생각이 들어서, 체크는 해주되 이동을 맨 마지막에 해주는 것으로 계획을 짜서 문제를 해결하였습니다.
스킬
이 문제는 상하좌우 4방향의 중력을 구현하는 것이 중요합니다. 중력을 구현하는 방법에는 여러가지가 있는데, 여기서는 사탕 두개만 이동하면 되므로, 가장 간단한 형태의 중력 구현이 적용됩니다. 기본형은 아래와 같은데, 말 그대로 벽을 만나기 전까지 좌표를 계속 업데이트하는 방식입니다. break 후의 x, y 좌표가 이동 후의 좌표이며, 가고자 하는 방향의 정수를 direction자리에 입력해 상하좌우, 혹은 8가지 방향의 중력을 한번에 구현할 수 있습니다.
dx = [1, -1, 0, 0] # 남북동서
dy = [0, 0, 1, -1]
x, y = 원래의 좌표
while True:
nx, ny = x+dx[direction], y+dy[direction]
if graph[nx][ny] == '빈칸':
x, y = nx, ny # 이동
elif graph[nx][ny] == '벽':
break # 멈춤
중력을 구현하였으니, 위에서 말했던 주의사항을 기억하며 풀이하겠습니다.
풀이
from collections import deque
def getInput():
N, M = map(int, input().split())
# 그래프를 받는 첫번째 방법
graph = [list(map(str, input())) for _ in range(N)]
# 그래프를 받는 두번째 방법
# graph = []
# for row in range(N):
# graph.append(list(map(str, input())))
for row in range(N):
for col in range(M):
if graph[row][col] == 'R':
Red = (row, col)
graph[row][col] = '.'
elif graph[row][col] == 'B':
Blue = (row, col)
graph[row][col] = '.'
return N, M, graph, Red, Blue
def gravity(Red, Blue, direction):
dx = [1, -1, 0, 0] # 남북동서
dy = [0, 0, 1, -1]
check = 0 # 빨강들어가면 1, 파랑들어가면 2 더해줄거임.
# 물론 check를 사용하지 않고 좌표값만 return해서 함수 바깥에서 비교하는 식으로 할 수도 있다.
Rx, Ry = Red
Bx, By = Blue
Other = False # 다른 구슬이 있었는가?
while True:
Rnx, Rny = Rx+dx[direction], Ry+dy[direction] # 범위 설정 안하나요? -> 상자라 벽이 무조건 감싸고있어서 괜찮다. 문제에 그렇게 가정해도 된다고 적혀있다.
if graph[Rnx][Rny] == '.':
if (Rnx, Rny) == Blue:
Other = True
Rx, Ry = Rnx, Rny
elif graph[Rnx][Rny] == '#':
if Other: # 다른 구슬이 있었다면
Rx, Ry = Rx-dx[direction], Ry-dy[direction] # 그 전으로
break
else: break # 아니라면 끝
elif graph[Rnx][Rny] == 'O':
check += 1
break
# 여기서 Red를 바꿔버리면, Blue를 검사할 때 Red가 또 발견된다. 그래서 나중에 해줄것이다.
Other = False # 다른 구슬이 있었는가?
while True:
Bnx, Bny = Bx+dx[direction], By+dy[direction]
if graph[Bnx][Bny] == '.':
if (Bnx, Bny) == Red:
Other = True
Bx, By = Bnx, Bny
elif graph[Bnx][Bny] == '#':
if Other: # 다른 구슬이 있었다면
Bx, By = Bx-dx[direction], By-dy[direction] # 그 전으로
break
else: break # 아니라면 끝
elif graph[Bnx][Bny] == 'O':
check += 2
break
return (Rx, Ry), (Bx, By), check
# ===== 실제 실행하는 부분 =====
N, M, graph, Red, Blue = getInput()
queue = deque([(Red, Blue, 0)])
flag = False
while queue:
r, b, turn = queue.popleft()
if turn == 10: continue
for i in range(4):
nr, nb, check = gravity(r, b, i)
if check == 0: queue.append((nr, nb, turn+1))
elif check == 1:
print(turn+1)
flag = True
break
if flag: break
else:
print(-1)
'삼성전자 코딩테스트 기출문제 > Python' 카테고리의 다른 글
외주 수익 최대화하기 (퇴사) (2) | 2023.11.26 |
---|---|
테트리스 블럭 안의 합 최대화 하기 (테트로미노) (1) | 2023.11.25 |
2048 게임 (2048 (Easy)) (1) | 2023.11.23 |
정육면체 굴리기 (주사위 굴리기) (0) | 2023.11.18 |
바이러스검사 (시험 감독) (0) | 2023.11.18 |