문제
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
최근 코드트리 빵이 전국적으로 인기를 얻어 편의점에서 해당 빵을 구하기 힘들어졌습니다. 빵을 구하고자 하는 m명의 사람이 있는데, 1번 사람은 정확히 1분에, 2번 사람은 정확히 2분에, ..., m번 사람은 정확히 m 분에 각자의 베이스캠프에서 출발하여 편의점으로 이동하기 시작합니다. 사람들은 출발 시간이 되기 전까지 격자 밖에 나와있으며, 사람들이 목표로 하는 편의점은 모두 다릅니다. 이 모든 일은 n*n 크기의 격자 위에서 진행됩니다.
코드트리 빵을 구하고 싶은 사람들은 다음과 같은 방법으로 움직입니다. 이 3가지 행동은 총 1분 동안 진행되며, 정확히 1, 2, 3 순서로 진행되어야 함에 유의합니다.
- 격자에 있는 사람들 모두가 본인이 가고 싶은 편의점 방향을 향해서 1 칸 움직입니다. 최단거리로 움직이며 최단 거리로 움직이는 방법이 여러가지라면 ↑, ←, →, ↓ 의 우선 순위로 움직이게 됩니다. 여기서 최단거리라 함은 상하좌우 인접한 칸 중 이동가능한 칸으로만 이동하여 도달하기까지 거쳐야 하는 칸의 수가 최소가 되는 거리를 뜻합니다.
- 만약 편의점에 도착한다면 해당 편의점에서 멈추게 되고, 이때부터 다른 사람들은 해당 편의점이 있는 칸을 지나갈 수 없게 됩니다. 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
- 현재 시간이 t분이고 t ≤ m를 만족한다면, t번 사람은 자신이 가고 싶은 편의점과 가장 가까이 있는 베이스 캠프에 들어갑니다. 여기서 가장 가까이에 있다는 뜻 역시 1에서와 같이 최단거리에 해당하는 곳을 의미합니다. 가장 가까운 베이스캠프가 여러 가지인 경우에는 그 중 행이 작은 베이스캠프, 행이 같다면 열이 작은 베이스 캠프로 들어갑니다. t번 사람이 베이스 캠프로 이동하는 데에는 시간이 전혀 소요되지 않습니다.
- 이때부터 다른 사람들은 해당 베이스 캠프가 있는 칸을 지나갈 수 없게 됩니다. t번 사람이 편의점을 향해 움직이기 시작했더라도 해당 베이스 캠프는 앞으로 절대 지나갈 수 없음에 유의합니다. 마찬가지로 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
이미 사람들이 도착한 편의점이나 출발한 적이 있는 베이스캠프의 경우 움직일 때 절대 지나갈 수 없는 공간임을 유의합니다. (예시에서는 빨간색으로 표시되어 있습니다.)
사람들이 위와 같은 방식으로 움직일 때 총 몇 분 후에 모두 편의점에 도착하는지를 구하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에는 격자의 크기 n과 사람의 수 m이 공백을 사이에 두고 주어집니다.
이후 n개의 줄에 걸쳐 격자의 정보가 주어집니다. 각 줄에 각각의 행에 해당하는 n개의 수가 공백을 사이에 두고 주어집니다.
0의 경우에는 빈 공간, 1의 경우에는 베이스캠프를 의미합니다.
이후 m개의 줄에 걸쳐 각 사람들이 가고자 하는 편의점 위치의 행 x, 열 y의 정보가 공백을 사이에 두고 주어집니다.
각 사람마다 가고 싶은 편의점의 위치는 겹치지 않으며, 편의점의 위치와 베이스캠프의 위치도 겹치지 않습니다.
- 2 ≤ n ≤ 15
- 1 ≤ m ≤ min(n2,30)
- m ≤ 베이스 캠프의 개수 ≤ n2−m
출력 형식
모든 사람이 편의점에 도착하는 시간을 출력하세요.
문제 조건에 의해 어떠한 사람이 원하는 편의점에 도달하지 못하게 되는 경우는 절대 발생하지 않음을 가정해도 좋습니다. 또한, 이동하는 도중 동일한 칸에 둘 이상의 사람이 위치하게 되는 경우 역시 가능함에 유의합니다.
풀이
아이디어
놓치지 말아야 할 조건은 못지가는 칸(벽)은 모든 행동이 끝난 이후 적용이 된다는 것, 매 순간의 최단거리를 구해야한 다는 것이다.
해야 할 일은 다음과 같다
- 맵 구성
- 사람 이동
- 도착 확인
- 베이스캠프 할당
맵 구성
필요한 자료구조를 정리해 보자.
- 베이스캠프 정보 저장
- 사람의 현재 좌표, 편의점 위치, 도착여부 저장
- 도착확인 리스트
- 못움직이는 자리 (= 벽) 저장
입력 좌표가 1부터 시작하기 때문에 헷갈리지 않게 인덱스를 조정하여 저장한다.
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
info = [list(map(int, input().split())) for _ in range(M)]
# 베이스캠프 좌표를 담음
base = [[i, j] for j in range(N) for i in range(N) if board[i][j] == 1]
# 사람 : {현재위치, 도착 편의점 위치, 도착 여부}
people = {idx + 1: [[], [info[idx][0] - 1, info[idx][1] - 1], False] for idx in range(M)}
arrive = [1] * len(people) # 도착한 사람을 저장, 도착:0, 아직 안함:1
walls = [[0]*N for _ in range(N)] # 더이상 지나가지 못하는 곳 저장
사람 이동
처음엔 한칸 이동이니까 이동 할 수 있는 칸에서 이동했을 때 편의점과의 거리가 가까워지는 방향을 선택하는 방법을 이용했다.
→ 테스트 케이스 98에서 오류가 난다.
테스트 케이스가 너무 커서 디버깅하기 힘들었다. 토론하기에 있는 다른 예들은 잘 통과해서 마음이 아팠다.. 알아내기 위해서..
디버깅 하다 보니 사람이 이동하지 못하는 칸이 나왔다.
이유는 이미 이동한 이후, 벽이 생겨 돌아가야 하는 경우에 멀어지는 방향으로 가야할 수 밖에 없기 때문이다.
5 3
0 0 0 0 0
0 1 0 1 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
3 1
3 3
4 2
그러면 어떻게 해야하는가??!!
문제에서 이미 언급 되어있다. “최단거리”로 움직이되 1칸만 이동함.
이동하는 순간마다 bfs를 이용해 최단거리를 구하면 된다.
꽤부리다가 낭비한 시간이 얼마인지..
격자에 사람이 있는 경우, 편의점과의 최단거리중 1칸만 움직인다
def move_people(info, key):
x, y, cx, cy = info[0][0], info[0][1], info[1][0], info[1][1]
route = []
# 방향마다 한칸 간 후, 최단거리 구하기
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
# 갈 수 없는 칸
if not is_board(nx, ny) or walls[nx][ny] == -1: # [nx, ny] in walls:
route.append(INF)
continue
route.append(bfs(nx, ny, cx, cy))
min_dist = min(route)
candi = [idx for idx in range(len(route)) if route[idx] == min_dist]
nx = x + dx[candi[0]]
ny = y + dy[candi[0]]
people[key][0] = [nx, ny]
# 도착한 경우 도착상태 on, 도착 리스트 추가
if [nx, ny] == [cx, cy]:
people[key][2] = True
arrive[key-1] = 0
도착 확인
이동이 끝난 후, 도착한 사람을 확인한다.
도착한 편의점은 더이상 가지못하는 벽이 되는데, 이때 벽 설정을 해준다.
미리 도착상태를 True로 만들어 주었기 때문에 벽설정만 해준다.
여기서 처음에 리스트 값으로 확인 했는데 어마어마한 소요시간이 들었다.
넘 놀래서 수정했다.
벽을 설정하는 board를 새로 만들어 벽이라면 더이상 지나가지 못하게 만듦.
# 2. 도착 확인
# 도착 확인 on이 된 사람들의 좌표를 벽으로 만듦
for key in people.keys():
if people[key][2]:
[x, y] = people[key][1]
walls[x][y] = -1
베이스 캠프 할당
편의점 - 베이스캠프까지 최단거리 계산 후 우선순위에 따라 선택한다.
우선순위는 [행, 열]을 오름차순으로 정렬한다.
베이스캠프로 선정 되면 더이상 못지나가기 때문에 벽 좌표에 추가함.
def select_base(cx, cy):
# 편의점 위치를 cx,cy로 받음
# 가장 가까운 베이스캠프 계산
route = []
# 베이스 캠프에서 편의점까지의 거리를 계산
for idx, [bx,by] in enumerate(base):
temp = bfs(bx, by, cx, cy)
route.append(temp)
min_distance = min(route)
# 거리가 최소인 후보 베이스캠프
candi = [base[i] for i in range(len(route)) if route[i] == min_distance]
# 우선순위를 고려한 베이스 캠프 정렬
candi.sort()
# 이미 선택된 베이스캠프 삭제
base.remove(candi[0])
# 이제 움직이지 못하는 벽으로 만듦
[x, y] = candi[0]
walls[x][y] = -1
return candi[0]
# 3. 베이스캠프 선택
# 모든 사람이 베이스 캠프를 가질 때 까지
if time <= M:
[x, y] = people[time][1] # 편의점 위치
base_x, base_y = select_base(x, y)
people[time][0] = [base_x, base_y]
코드
import sys
from collections import deque
# 0: 상, 1:우, 2:좌, 3:하
dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]
INF = 1000000000000000000
def is_board(x, y):
return 0<= x < N and 0<= y < N
def bfs(x, y, cx, cy):
q = deque()
visited = [[0] *N for _ in range(N)]
q.append([x, y, 1])
visited[x][y] = 1
# print(f"{x, y}에서 {cx, cy}까지 가는 최단 거리 구하는 중...")
while q:
x, y, route = q.popleft()
if [x, y] == [cx, cy] :
return route
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
# 격자 밖인 경우
if not is_board(nx, ny):
continue
# 방문 하지 않고, 벽이 아닌 경우
if visited[nx][ny] == 0 and walls[nx][ny] != -1 :# [nx, ny] not in walls:
visited[nx][ny] = 1
q.append([nx, ny, route+1])
if [nx, ny] == [cx, cy]:
return route
# 어디에도 못가는 경우 추가
return INF
def select_base(cx, cy):
# 편의점 위치를 cx,cy로 받음
# 가장 가까운 베이스캠프 계산
route = []
# 베이스 캠프에서 편의점까지의 거리를 계산
for idx, [bx,by] in enumerate(base):
temp = bfs(bx, by, cx, cy)
route.append(temp)
min_distance = min(route)
# 거리가 최소인 후보 베이스캠프
candi = [base[i] for i in range(len(route)) if route[i] == min_distance]
# 우선순위를 고려한 베이스 캠프 정렬
candi.sort()
# 이미 선택된 베이스캠프 삭제
base.remove(candi[0])
# 이제 움직이지 못하는 벽으로 만듦
[x, y] = candi[0]
walls[x][y] = -1
return candi[0]
def move_people(info, key):
x, y, cx, cy = info[0][0], info[0][1], info[1][0], info[1][1]
route = []
# 방향마다 한칸 간 후, 최단거리 구하기
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
# 갈 수 없는 칸
if not is_board(nx, ny) or walls[nx][ny] == -1: # [nx, ny] in walls:
route.append(INF)
continue
route.append(bfs(nx, ny, cx, cy))
min_dist = min(route)
candi = [idx for idx in range(len(route)) if route[idx] == min_dist]
nx = x + dx[candi[0]]
ny = y + dy[candi[0]]
people[key][0] = [nx, ny]
# 도착한 경우 도착상태 on, 도착 리스트 추가
if [nx, ny] == [cx, cy]:
people[key][2] = True
arrive[key-1] =
sys.stdin = open('input.txt', 'r')
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
info = [list(map(int, input().split())) for _ in range(M)]
# 베이스캠프 좌표를 담음
base = [[i, j] for j in range(N) for i in range(N) if board[i][j] == 1]
board = [[0 for i in line] for line in board]
# 사람 : {현재위치, 도착 편의점 위치, 도착 여부}
people = {idx + 1: [[], [info[idx][0] - 1, info[idx][1] - 1], False] for idx in range(M)}
arrive = [1] * len(people) # 도착한 사람을 저장, 도착:0, 아직 안함:1
walls = [[0]*N for _ in range(N)] # 더이상 지나가지 못하는 곳 저장
time = 0
# 0. 편의점에 모두 도착할 때 까지
while sum(arrive) != 0:
time += 1
# 1. 이동
for key in people.keys():
# 이미 도착한 경우 이동x
if people[key][2] or people[key][0] == []:
continue
move_people(people[key], key)
# 2. 도착 확인
# 도착 확인 on이 된 사람들의 좌표를 벽으로 만듦
for key in people.keys():
if people[key][2]:
[x, y] = people[key][1]
walls[x][y] = -1
# 3. 베이스캠프 선택
# 모든 사람이 베이스 캠프를 가질 때 까지
if time <= M:
[x, y] = people[time][1] # 편의점 위치
base_x, base_y = select_base(x, y)
people[time][0] = [base_x, base_y]
print(time)
'프로그래밍 > Python' 카테고리의 다른 글
| [코드트리] 메이즈 러너 / Python(파이썬) (2) | 2024.04.12 |
|---|---|
| [프로그래머스] 퍼즐 조각 채우기 / 깊이/너비 우선 탐색(DFS/BFS) / Python (0) | 2024.04.12 |
| [코드트리] 루돌프의 반란 / Python(파이썬) (0) | 2024.04.08 |
| [코드트리] 왕실의 기사대결 / 파이썬(python) (0) | 2024.04.01 |
| [프로그래머스] 방의 개수 / 그래프 / python (0) | 2024.03.20 |
댓글