[코테준비] 삼성17. 코드트리: 코드트리 빵 python + 코드트리의 채점 무한로딩

코드트리의 채점 무한로딩

와 이번문제는 예제 맞추고, 바로 채점이 100%까지 올라가서, '와 바로 맞췄다' 했는데, 계속 무한 로딩 떠서 어딘가 틀린건가... 계속 생각하게 되었다. 보니까 유저가 많아서 그런 문제가 생기는 것 같다. 자신의 코드가 100%나 유사하게 높게 올라갔는데, 무한 로딩이 돈다면, 그냥 서버 문제겠거니 하고 넘어가도 좋을 것 같다. 한 20번 제출해서 같은 코드로 통과 했다. 내 코드가 수행시간이나 메모리가 다른코드에 비해 높지 않은 것으로 봐서, 그냥 서버 문제인 것 같다. 지금 보니 많은 사람들이 같은 문제를 격고 있는 것 같다. 역시 삼성 코테가 코앞이라 그런가. 얼굴도 모르지만 같이 준비하는 느낌이 들어 좋군. 더 열심히 해야지

 

---

 

코드트리 빵

• 링크: https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description
• 기출: 삼성 SW 역량테스트 2022 하반기 오후 1번 문제
• 난이도:골드 2
• 분류: 시뮬레이션, BFS
• 직접 푼 여부: O  (문제이해: 15m, 코드 틀 짜기(노트): 60m, 코드 짜기: 60m,  디버깅 60m) 
• 언어: 파이썬

풀이 노트

이번 풀이 노트는 좀 잘 못적은 것 같다. 그래서 아래 사진은 그냥 참고하고,  (1) 아래 글로 정리해 놓은 것과  (2)코드에 적힌 주석과 (3)아래 빨간색으로 정리한 실수할 수 있는 것을 보는게 좋을 듯 하다.

 

1. 풀이 순서

(1) 문제 이해 - in/out

(2) 정의할 function 정하기 & 그 안에 중요한 사항 

• [1] 격자내 움직임 -  bfs 상좌우상 순
• [2] 도착한 곳 사람 없으면, 멈추게 - 사람이 있는지 확인하고, 표시. → 도착한 것을 써놓는 리스트와 못지나가는 곳을 표시하는 2차원 배열이 필요
• [3] basecamp찾고, 이동하기 - 이 안에서 아예 그 basecamp에 사람 없으면 못지나가는 곳 표시
• [4] 다 도착했는지 확인 - 다 도착하면, 끝나니까 확인  → 이걸 격자내 있는 사람들의 좌표담고 있는 list를 이용하여 풀었다.

(3) 사용할 변수들 생각

→ 이게 생각보다 까다로웠다. 

• 사람들의 격자 속 위치 list: grid_people_list  → 원래 격자내에 있는 수만큼 len를 하려했으나, 그러니까 문제가 생겨서 격자내에 없거나 도착하면 (-1,-1)로 표시하였다. 그래서 이는 항상 len( grid_people_list   )=m이다. 
• 이제 사람들만 없어지면, 통행못하는 곳 후보 list: semi
• 못가는 곳 표시하는 2차원 list: cannot_go_map

 

2. 주의 사항 (내가 놓쳤던 것들)

(1) bfs를 하며 visited 꼭 쓰기. 그리고 true가 되는 시점은 q에 append하기 전

(2) 격자내 움직임에서는 경로를 찾고, 그 경로의 첫번째로 움직여야하므로 path를 저장해야한다. 이 path가 동시에 업데이트 되지 않게, copy.deepcopy로 해서 update해줄 것

(3) basecamp를 찾을 때는 격자내 움직임과 다르게 최소거리에 있는 것들을 다 돌아보고, 결정해야한다. 그래서 qlen를 사용해야한다(격자내 움직임은 상좌우하로 움직이고 찾으면 바로 멈추면 된다). 한단계가 끝나면, 그 안에 도착한 적이 있으면, 끝내면 된다. 

while q:
       qlen = len(q)
       for _ in range(qlen):
              "작업"
       if arrived = True: break

+ basecamp 후보를 list로 받고, 이후에 sorting해도 되지만, 아예 처음 돌때부터 찾으면 더 효율적이다. (저번 16번문제를 풀 때, 다른 사람 코드를 본 것을 써먹는다! - 역시 다른 사람코드도 많이 봐야 는다.)

if basecamp_map[newr][newc]==1: # basecamp에 도착하면
      arrived=True
      if newr<br: br, bc = newr, newc
      elif newr == br:
               if newc<bc: br, bc = newr, newc

(4) basecamp를 찾을 때, visited는 시도한 곳에 True가 되어야하므로, 범위를 벗어나거나 이미 갔거나 못가는 곳이 아니면 True를 하면 된다. 그리고 처음 있던 곳도 True! 

 

---

노트 정리 방식은 다음과 같다. - 이번엔 필기가 좀 더러워서 굳이 볼 필요 없을 것 같다. 

• 연필: 문제를 보면서 적은 것
• 연필(두번째 사진): 어떻게 풀어가야할지 계획
• 파란펜: 주의해야할 것
• 빨간펜: 놓쳐서 디버깅 때 찾은 것 & 공부해야할 것 

 

문제 이해

 

코드 틀 짜기

 

정답 코드 💻

# 코드트리 빵
import sys
from collections import deque
import copy

input = sys.stdin.readline
def int_minus(x):
    return int(x)-1
# input [0] --------------------------------------
n, m = map(int, input().split())
basecamp_map=[list(map(int, input().split())) for _ in range(n)] # 1: basecamp 0: blank
store_index  =[tuple(map(int_minus,input().split())) for _ in range(m)] # [(r,c), (r,c)]

# def --------------------------------------
def grid_move(i):
    """[1] grid에 있는 사람 움직임"""
    global semi, grid_people_list
    nowr, nowc = grid_people_list[i]
    if nowr ==-1: # 이미 도착하거나, 출발 안했으면, 움직이지 않음
        return 
        
    # 1) 가장 가까운 path 찾기 (path는 처음 움직이는 방향만 check하면 됨)
    # bfs
    visited = [[False] * n for _ in range(n)]
    q = deque()
    visited[nowr][nowc] = True
    q.append((nowr, nowc, []))
    first_dir=5
    while q:
        r, c, path = q.popleft()
        for direction in range(4):
            newr, newc = r+dr[direction], c+dc[direction]
            # 못가는 곳이면 넘어가기
            if not(0<=newr<n) or not(0<=newc<n) or cannot_go_map[newr][newc] or visited[newr][newc]:
                continue
            # 도착 하면, 해당 path가 가장 짧은 것! -> 끝!!! 길찾기 끝내고(for break, while q =[]), 해당 path로 한칸 움직이기
            if (newr, newc) == store_index[i]:
                if len(path)>0:
                    first_dir = path[0]#무조건 도착
                else:
                    first_dir= direction
                q =[]
                break
            temppath=path[:]
            temppath.append(direction)
            visited[newr][newc] = True
            q.append((newr,newc,temppath))

    # 2) 한칸 옮기기 - 편의점 도착했는지 check
    oner, onec = nowr+dr[first_dir], nowc+dc[first_dir]
    # 도착하면, 1) grid_people_list에서 없애기 2) semi에 표시
    if (oner, onec) ==store_index[i]:
        grid_people_list[i] =(-1,-1)
        semi.append((oner, onec))
    else:
        grid_people_list[i] = (oner, onec)
    return



def basecamp_move(number):
    """[3] 시간되면, basecamp로 나오기"""
    # semi update  & 만약 그 위치에 사람 없으면, 바로 못가게 하는 것 까지
    global semi, grid_people_list
    # 1) basecamp찾기
    br, bc = n, n #갈 basecamp위치 (초기화- 안되는 값으로. 큰값 중 최솟값)
    arrived = False
    q=deque()
    q.append(store_index[number]) #편의점에서 부터 출발
    visited =[[False]*n for _ in range(n)]
    visited[store_index[number][0]][store_index[number][1]]=True

    while q:
        qlen = len(q)
        for _ in range(qlen):
            r, c = q.popleft()
            for direction in range(4):
                newr,newc = r+dr[direction], c +dc[direction]
                if not(0<=newr<n) or not(0<=newc<n) or cannot_go_map[newr][newc] or visited[newr][newc]:
                    continue
                visited[newr][newc] = True
                if basecamp_map[newr][newc]==1: # basecamp에 도착하면
                    arrived=True
                    if newr<br:
                        br, bc = newr, newc
                    elif newr == br:
                        if newc<bc:
                            br, bc = newr, newc
                elif not arrived: # 도착안했고, 도착한 적 없으면, 한단계 깊게 가봄 아니면 끝
                    q.append((newr, newc))
        if arrived:
            break

    # 2) base camp deactivate 결정
    if (br, bc) in grid_people_list:  #거기에 사람 있으면, 다음에 다시 검사
        semi.append((br,bc))
    else: # 사람 없으면 바로 deactivate
        cannot_go_map[br][bc] = True
    grid_people_list[number] = (br,bc) # 해당 사람 위치 시키기
    return


def cannot_go_check():
    """[2] 도착했고, 거기에 사람 없으면 deactivate"""
    global semi, cannot_go_map
    tempsemi = semi[:]
    semi =[]
    for location in tempsemi:
        if location in grid_people_list: #거기에 사람이 있으면 다음에 다시 check
            semi.append(location)
            continue
        else:
            cannot_go_map[location[0]][location[1]] = True
    return
def end():
    total = len(grid_people_list)
    cnt=0
    for i in range(total):
        if (-1,-1) == grid_people_list[i]:
            cnt+=1
    return True if cnt==m else False
#
# main --------------------------------------
grid_people_list = [(-1,-1) for _ in range(m)] # (r, c) 만약 출발전이나 도착후면, (-1,-1)
semi = []  # (r,c) 해당위치에 사람이 다 나가면, cannot_go[r][c] True로 바꾸고, 여기선 없앰
cannot_go_map = [[False]*n for _ in range(n)] # 못움직이는 위치
dr = [-1, 0,0,1] #상좌우하
dc = [0,-1,1,0]
minute =1
while True:
    # 1) 격자내 움직임 ------------------
    for i in range(m):
        # 비어있으면, 통과됨
        grid_move(i)
    # 1-1) 움직임 이후, 못가는 곳 표시 ------------------
    if len(semi)!=0:
        cannot_go_check()

    # 2) basecame로 이동 (m분이 지나면, 이 과정 필요 없음) ------------------
    if minute<=m:
        basecamp_move(minute-1) # 현재 시간과 같은 번호인 사람이 basecamp로 움직임

    # 3) End check ------------------
    if end():
        # 다 도착하면, while 문 break
        break

    minute  +=1 # 시간 흐름

print(minute) # 도착 시간

 

정답!