[코딩테스트] CodeTree - 코드트리 빵
1. 문제
출처
문제
최근 코드트리 빵이 전국적으로 인기를 얻어 편의점에서 해당 빵을 구하기 힘들어졌습니다. 빵을 구하고자 하는 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(n^2,30)
- m ≤ 베이스 캠프의 개수 ≤ n^2−m
출력 형식
모든 사람이 편의점에 도착하는 시간을 출력하세요.
문제 조건에 의해 어떠한 사람이 원하는 편의점에 도달하지 못하게 되는 경우는 절대 발생하지 않음을 가정해도 좋습니다.또한, 이동하는 도중 동일한 칸에 둘 이상의 사람이 위치하게 되는 경우 역시 가능함에 유의합니다.
2. 문제 풀이
삼성전자 기출문제 중 시뮬레이션 문제는 흐름이 긴 대신 차근차근 풀이하면 다른 알고리즘 활용 문제보다 어렵지 않다고 생각됩니다. 같은 맥락으로 문제를 풀이해보겠습니다.
나의 문제 풀이 방법
시험장에서 떠올린 사고 과정을 통한 풀이를 서술하였습니다. 정해가 아니며, 실제로 여러번 bfs를 실행하여 비효율적인 부분이 있습니다.
1. 문제 정리
먼저 문제를 읽고 정리하며
- 문제 입출력 범위
- 어떤 함수를 구현해야 할지
- main 문을 어떻게 구성할지
의 흐름대로 문제 풀이를 진행했습니다.
해당 흐름을 통해 다음과 같이 문제를 정리할 수 있습니다.
💡 사람 M명 - M번 사람은 M분에 베이스캠프에서 출발
NxN 격자
1분에 일어나는 3가지 행동
- 가고 싶은 방향으로 최단거리 1칸 이동, {상,좌,우,하} 순서대로 -> 최단거리 구하는 bfs에서 첫 step을 저장해야 함
- 편의점 도달 시 편의점에 멈추고 다른 사람들은 해당 편의점 지나갈 수 없음
- 현재 시간 t이고 t<=M 이면 t번 사람은 자신이 가고 싶은 편의점과 가장 가까이 있는 베이스 캠프에 들어감 {행,열} 순서대로, 이때 해당 베이스캠프는 더 이상 들어갈 수 없음
Sol. 구해야 하는 것 : 모든 사람이 편의점에 도착하는 시간 입력 범위가 적으므로 완전 탐색으로 solve 가능
-
현재 위치에서 원하는 편의점까지 최단거리를 구하는 bfs 구현 1-1. 해당 거리까지 중 첫번째 1칸 구함
-
M번 사람의 목표인 M번 편의점에 대해 어느 베이스캠프가 가장 가까운지 모든 베이스캠프에 대해 1을 적용하여 최단거리 구하고 사람 위치시키기
-
1,2 과정을 모든 사람이 원하는 편의점에 도달할 때까지 반복
2. 코드 작성
위와 같이 정리한 내용을 바탕으로 크게 3개로 코드 작성 부분을 나눠볼 수 있습니다.
- 값 입력받기 및 필요한 변수 및 배열 선언
- 필요한 함수 선언
- main문 작성
2-1. 값 입력받기 및 필요한 변수 및 배열 선언
from collections import deque : 문제에서 최단거리를 구해야하기 때문에 bfs를 통해 해결하기 위해 deque를 import해줍니다.
N,M = map(int,input().split()) :첫 번째 줄에는 격자의 크기 n과 사람의 수 m이 공백을 사이에 두고 주어집니다.
graph = [list(map(int,input().split())) for _ in range(N)] : 이후 m개의 줄에 걸쳐 각 사람들이 가고자 하는 편의점 위치의 행 x, 열 y의 정보가 공백을 사이에 두고 주어집니다. 이때 빈 공간은 0으로, 베이스캠프의 위치는 1로 주어집니다.
stores = list(list(map(int,input().split())) for _ in range(M)) : 각 사람마다 가고 싶은 편의점의 위치는 겹치지 않으며, 편의점의 위치와 베이스캠프의 위치도 겹치지 않습니다.
가고자 하는 편의점의 입력 범위가 1부터 주어지기 때문에 list 인덱싱을 위하여 for문을 통해 행과 열의 범위를 1씩 감소시켜줍니다.
# 1씩 감소
for idx in range(len(stores)):
r,c = stores[idx]
stores[idx] = [r-1,c-1]
base_store = [[0]*N for _ in range(N)]: 격자 내에 지나갈 수 없는 위치가 생성되는 2가지 경우가 존재합니다.
- 사람이 베이스캠프에 도착했을 때
- 편의점에 도착했을 때
위 두 경우 발생 시 해당 위치를 더 이상 지날 수 없도록 하는 정보를 저장하는 2차원 배열 base_store 를 선언해줍니다.
people_pos = [[[] for _ in range(N)] for _ in range(N)] : 사람들이 베이스 캠프에서부터 편의점으로 도착할때까지의 위치정보를 저장하는 2차원 배열을 선언해줍니다.
이때 중요한 점은 “한 위치에 여러 사람이 있는 경우” 가 발생할 수 있다는 점입니다.
따라서 각 원소를 리스트 형태로 갖도록 해주고 append함수와 remove함수를 사용해 해당 위치를 거쳐가는 사람들의 정보를 업데이트해주었습니다.
(처음 문제 풀이 시에는 위 사항을 고려하지 못해 시간을 소요하였습니다.)
# 상,좌,우,하
dr = [-1,0,0,1]
dc = [0,-1,1,0]
이후 가고 싶은 방향으로 최단거리 1칸을 이동할 때 {상,좌,우,하}의 우선순위대로 이동하므로 이를 고려하여 dr,dc를 선언해줍니다.
from collections import deque
N,M = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(N)] # 0 - empty, 1 - basecamp
stores = [(list(map(int,input().split())) for _ in range(M))]
for idx in range(len(stores)):
r,c = stores[idx]
stores[idx] = [r-1,c-1]
base_store = [[0]*N for _ in range(N)] # base camp와 store 도착했을 경우 저장
people_pos = [[[] for _ in range(N)] for _ in range(N)]
# base 위치 구하기 ------------
bases = deque()
for r in range(N):
for c in range(N):
if graph[r][c] == 1:
bases.append((r,c))
# 상,좌,우,하
dr = [-1,0,0,1]
dc = [0,-1,1,0]
2-2. 필요한 함수 선언
def in_range(in_r,in_c):
if 0 <= in_r < N and 0 <= in_c < N:
return True
return False
def is_empty(is_r,is_c):
if base_store[is_r][is_c] != -1:
return True
return False
빈번하게 사용되는 새로운 r과 c의 범위가 0~N 사이에 있는지를 검사하는 in_range 함수와 격자의 특정 위치가 (베이스캠프, 편의점 도착) 의 경우가 아닌지를 검사하는 is_empty 함수를 선언했습니다.
❗ 필요한 함수들
bfsbfs통해 최단거리 구해주는 함수move_to_store격자에서 사람을 편의점을 향해 이동시키는 함수move_to_base사람을 편의점까지 최단거리인 베이스캠프에 위치시키는 함수
bfs
bfs를 통해 현재 위치해서 목적지로 가는 최단거리를 구했습니다.
입력 인자 : {현재 위치, 사람의 번호}
사람의 번호를 입력받으면 앞서 선언한 stores 리스트를 통해 목적지의 위치를 알 수 있습니다.
if cnt == 0: # 첫번째 step이면 step에 해당하는 방향을 direction으로 저장
q.append((nr,nc,cnt+1,i))
else: # 두번째 이상 step에서는 첫번째 step을 계속 가져갈 수 있도록 함
q.append((nr,nc,cnt+1,direction))
이때,
💡 1. 가고 싶은 방향으로 최단거리 1칸 이동, {상,좌,우,하} 순서대로 -> 최단거리 구하는 bfs에서 첫 step을 저장해야 함
첫 step을 저장하기 위해 조건문을 통해 첫번째 step이라면 해당 step에 해당하는 방향을 저장하는 구문을 추가해줬습니다.
return -1,-1 # 현재 위치에서 목적지로 갈 수 없는 경우
또한, 모든 경우의 수를 고려하는 베이스캠프→편의점 최단거리 찾는 단계에서 현재 위치에서 목적지로 갈 수 없는 경우가 발생할 수 있습니다. 이를 위해 만약 while문을 모두 돌았음에도 direction과 cnt를 return하지 못했다면 (-1,-1)을 출력하도록 했습니다.
def bfs(now_r,now_c,n_m):
dst_r,dst_c = stores[n_m-1]
q = deque()
cnt = 0
q.append((now_r,now_c,cnt,-1))
visited = [[0]*N for _ in range(N)]
visited[now_r][now_c] = 1
while q:
r,c,cnt,direction = q.popleft()
if r == dst_r and c == dst_c:
return direction,cnt
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if in_range(nr,nc) and is_empty(nr,nc) and visited[nr][nc] == 0:
visited[nr][nc] = 1
if cnt == 0: # 첫번째 step이면 step에 해당하는 방향을 direction으로 저장
q.append((nr,nc,cnt+1,i))
else: # 두번째 이상 step에서는 첫번째 step을 계속 가져갈 수 있도록 함
q.append((nr,nc,cnt+1,direction))
**return -1,-1 # 현재 위치에서 목적지로 갈 수 없는 경우**
move_to_store
people_pos 리스트 내에 위치한 사람들을 최단 거리로 이동시키는 함수입니다.
for r in range(N):
for c in range(N):
if people_pos[r][c]:
if len(people_pos[r][c]) > 1: # 한 위치에 2명 이상 있는 경우
for PERSON_NUMBER in people_pos[r][c]:
people.append((PERSON_NUMBER,r,c))
else: # 한 위치에 한명만 있는 경우
people.append((people_pos[r][c][0],r,c)) # number,r,c 저장
people 리스트를 선언하고 people_pos 리스트에서
- 한 위치에 2명 이상의 사람이 있는 경우
- 한 위치에 한명만 있는 경우
를 나눠서 people에 추가해줍니다.
for p_n,r,c in people:
direction,_ = bfs(r,c,p_n)
nr = r + dr[direction]
nc = c + dc[direction]
dst_r,dst_c = stores[p_n-1]
if nr == dst_r and nc == dst_c:
base_store[nr][nc] = -1
arrive_cnt += 1
people_pos[r][c].remove(p_n)
else:
people_pos[r][c].remove(p_n)
people_pos[nr][nc].append(p_n)
이후 각 사람의 번호와 위치를 통해 bfs 함수를 실행시켜 방향을 구해주고 이동시킵니다.
- 만약 이동한 위치가 목적지라면
base_store에 업데이트하고 main을 위해arrive_cnt를 1 증가시킵니다. - 만약 이동한 위치가 목적지가 아니라면 이동시키고 종료합니다.
위 두 과정 모두 이전 위치에서 사람의 번호를 지워줘야 함을 유의합니다.
move_to_base
격자 밖에 사람이 있을때 어느 베이스에 위치시킬지 결정하는 함수입니다.
def move_to_base(person_n):
if not person_n:
return
search = []
for r,c in bases:
if base_store[r][c] != -1:
_,cnt = bfs(r,c,person_n)
if cnt == -1:
continue
search.append([cnt,r,c])
search.sort(key=lambda x : (x[0],x[1],x[2]))
# print("search:",search)
_,r,c = search[0]
base_store[r][c] = -1
people_pos[r][c].append(person_n)
if base_store[r][c] != -1: : 만약 해당 위치에 이미 이전 사람이 방문했다면 검사하지 않습니다.
if cnt == -1: : 만약 (r,c)에 해당하는 베이스 위치에서 목적지 편의점으로 갈 수 없으면 (=bfs를 통해 return 받은 cnt 값이 -1) continue 를 통해 아래 search.append([cnt,r,c]) 를 pass합니다.
이후 1. cnt 적은 순서, 2. 행과 열 순서 대로 정렬한 후 첫 번째 원소의 위치에 사람을 이동시킵니다.
def actions():
move_to_store()
move_to_base(input_n)
위 함수들을 한번에 실행시키는 함수를 선언합니다.
2-3. main
time = 0
arrive_cnt = 0
while True:
if arrive_cnt == M:
print(time)
break
if time < M:
input_n = time + 1
else:
input_n = 0
actions()
time += 1
while문을 통해 모든 사람이 편의점에 도착할때까지 함수들을 반복합니다.
- 값 입력받기 및 필요한 변수 및 배열 선언
- 필요한 함수 선언
- main문 작성
3. 소스코드
'''
사람 M명 - M번 사람은 M분에 베이스캠프에서 출발
NxN 격자
1분에 일어나는 3가지 행동
1. 가고 싶은 방향으로 최단거리 1칸 이동, {상,좌,우,하} -> 최단거리 구하는 bfs에서 첫 step을 저장해야 함
2. 편의점 도달 시 편의점에 멈추고 다른 사람들은 해당 편의점 지나갈 수 없음
3. 현재 시간 t이고 t<=M 이면 t번 사람은 자신이 가고 싶은 편의점과 가장 가까이 있는 베이스 캠프에 들어감
{행,열}, 이때 해당 베이스캠프는 더 이상 들어갈 수 없음
Sol.
구해야 하는 것 : 모든 사람이 편의점에 도착하는 시간
입력 범위가 적으므로 완전 탐색으로 solve
1. 현재 위치에서 원하는 편의점까지 최단거리를 구하는 bfs 구현
1-1. 해당 거리까지 중 첫번째 1칸 구함
2. M번 사람의 목표인 M번 편의점에 대해 어느 베이스캠프가 가장 가까운지 모든
베이스캠프에 대해 1을 적용하여 최단거리 구하고 사람 위치시키기
한 위치에 여러 사람이 있는 경우??
'''
# 1. 값 입력받기 및 필요한 변수 및 배열 선언
from collections import deque
N,M = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(N)] # 0 - empty, 1 - basecamp
stores = list(list(map(int,input().split())) for _ in range(M))
for idx in range(len(stores)):
r,c = stores[idx]
stores[idx] = [r-1,c-1]
base_store = [[0]*N for _ in range(N)] # base camp와 store 도착했을 경우 저장
people_pos = [[[] for _ in range(N)] for _ in range(N)]
# base 위치 구하기 ------------
bases = deque()
for r in range(N):
for c in range(N):
if graph[r][c] == 1:
bases.append((r,c))
# 상,좌,우,하
dr = [-1,0,0,1]
dc = [0,-1,1,0]
# 2. 필요한 함수 선언
def in_range(in_r,in_c):
if 0 <= in_r < N and 0 <= in_c < N:
return True
return False
def is_empty(is_r,is_c):
if base_store[is_r][is_c] != -1:
return True
return False
def bfs(now_r,now_c,n_m):
dst_r,dst_c = stores[n_m-1]
q = deque()
cnt = 0
q.append((now_r,now_c,cnt,-1))
visited = [[0]*N for _ in range(N)]
visited[now_r][now_c] = 1
# print(f"현재({now_r},{now_c}), {n_m} 목적지 : ({dst_r},{dst_c})")
while q:
r,c,cnt,direction = q.popleft()
if r == dst_r and c == dst_c:
return direction,cnt
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if in_range(nr,nc) and is_empty(nr,nc) and visited[nr][nc] == 0:
visited[nr][nc] = 1
if cnt == 0: # 첫번째 step이면 step에 해당하는 방향을 direction으로 저장
q.append((nr,nc,cnt+1,i))
else: # 두번째 이상 step에서는 첫번째 step을 계속 가져갈 수 있도록 함
q.append((nr,nc,cnt+1,direction))
return -1,-1 # 현재 위치에서 목적지로 갈 수 없는 경우
def move_to_store():
global arrive_cnt
people = []
for r in range(N):
for c in range(N):
if people_pos[r][c]:
if len(people_pos[r][c]) > 1: # 한 위치에 2명 이상 있는 경우
for PERSON_NUMBER in people_pos[r][c]:
people.append((PERSON_NUMBER,r,c))
else: # 한 위치에 한명만 있는 경우
people.append((people_pos[r][c][0],r,c)) # number,r,c 저장
for p_n,r,c in people:
direction,_ = bfs(r,c,p_n)
nr = r + dr[direction]
nc = c + dc[direction]
dst_r,dst_c = stores[p_n-1]
if nr == dst_r and nc == dst_c:
base_store[nr][nc] = -1
arrive_cnt += 1
people_pos[r][c].remove(p_n)
else:
people_pos[r][c].remove(p_n)
people_pos[nr][nc].append(p_n)
def move_to_base(person_n):
if not person_n:
return
search = []
for r,c in bases:
if base_store[r][c] != -1:
_,cnt = bfs(r,c,person_n)
if cnt == -1:
continue
search.append([cnt,r,c])
search.sort(key=lambda x : (x[0],x[1],x[2]))
# print("search:",search)
_,r,c = search[0]
base_store[r][c] = -1
people_pos[r][c].append(person_n)
def actions():
move_to_store()
move_to_base(input_n)
# 3. main
time = 0
arrive_cnt = 0
while True:
if arrive_cnt == M:
print(time)
break
if time < M:
input_n = time + 1
else:
input_n = 0
actions()
time += 1
4. 문제후기
2022년 하반기 삼성전자 SW역량테스트 기출문제를 복기한 코드트리 빵 문제를 다시 풀이해보았습니다.
소요시간
- 시험장 : 2시간30분 → 테스트케이스 6번 잡아내지 못해 이후 1시간30분동안 디버깅했지만 실패..
- 코드트리 복기 문제 풀이 : 1시간 40분
시험장에서 느낀 점
- 연습량과 경험 부족으로 문제를 차근차근 읽고 해석하지 못함 → 더 많은 시간 소요
- 온라인 상으로 복기되어 공개된 기출문제들보다 입력값의 범위나 서술 등이 다름
- 실제 시험장에서는 문제에 대한 정보가 일절 공개되지 않음(ex. 어떤 알고리즘이 필요한 문제인지, 문제의 난이도는 어느정도인지) → 문제에 대한 정보 없이 문제 해결하는 연습 필요
- 온라인 시험보다 오프라인 시험이 체력적, 심리적으로 더 부담될 수 밖에 없음 → 많은 연습 및 체력 관리 통해 보완하기
또한 위 풀이 과정을 통해 풀고 나서 코드 트리에 공개된 풀이 코드를 보니 제 풀이가 불필요하게 여러번 bfs를 실행하는 비효율적인 풀이임을 알게 되었습니다.
# debug 내역
'''
1. 격자의 한 위치에 여러 사람이 존재할 수 있는 경우 고려하지 않은 부분 수정
Sol.
people_pos 를 list를 요소로 갖는 2차원 배열로 수정
기존의 people_pos는 base_store 변수로 별도로 생성하여 base와 store의 경우를 -1로 저장할 수 있도록 함
2. 편의점의 위치 범위(1부터 시작, list indexing은 0부터 시작) 고려하지 않은 부분 수정
Sol. for문 통해서 1씩 줄여주기
3. bfs에서 현재 위치에서 목적지로 갈 수 없는 경우 고려하지 않았던 부분 수정
Sol. while문에서 return에 도달하지 않고 while문 밖으로 나올 경우 -1과 -1을 return하여 move_to_base() 함수에서 -1을 출력값으로 받았을 때, if-continue문 실행되게 함
'''
특히 위와 같은 디버깅 과정을 복기 문제 풀이 시에 거쳤는데, 시험장에서는 완벽하게 디버깅을 수행하지 못해 테스트케이스를 모두 잡아내지 못했습니다.
6번 테스트케이스에서 답이 29가 아닌 27이 나온 경우였는데
시험 이후에 틀렸던 이유를 알게되었습니다.
💡 한 사람 이동할때마다 텐트 치기 X → 도착한 모든 인원 이동 후 텐트치기 O
복기된 문제에서는 구현 과정을 순서대로 명시적으로 서술해줘서 더 수월하게 풀이할 수 있었지만, 현장에서는 긴장감 때문인지 문제를 제대로 읽고 해결하지 못했습니다. 😢
다시 풀이하니 이전 기출문제들과 비슷한 백준 골드 정도의 문제였던 것 같습니다.
Leave a comment