삼성 SW역량테스트 기출 / 2022 하반기 오후 1번 문제 코드트리 빵 / Python 파이썬

 

*문제 출처는 코드트리에 있습니다.

 

삼멘

문제 제목: 코드트리 빵 - bfs

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

---

나의 풀이

 

처음에 편의점과 베이스 캠프가 가까운 경로 ? -> abs(ex-x) + abs(ey-y) 처럼 구해야지~ 했다가 피를 봤다.

 

최단경로는 무조건 bfs 인거 잊지말자..

처음에 bfs 로 안해서 틀린코드

from collections import deque

n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
man = {i + 1: list(map(int, input().split())) for i in range(m)}
# 2면 못지나가는 베이스캠프, 편의점 (위치)
for i in man:
    man[i][0] -= 1
    man[i][1] -= 1


### 깊은 복사 ###
# TODO: 해당 턴 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
# 사람들은 동일한 칸에 있을 수 있음
# 사람들이 목표하는 편의점은 모두 다름
# 1분 동안 1,2,3 순서로 진행
def bfs(sx,sy,tx,ty):
    queue = deque([[sx,sy]])
    visited = [[False]*n for _ in range(n)]
    visited[sx][sy] = True
    # 최단경로를 구하는거지, 거리가 가까운 방향으로 이동만 하는게 답은 아님
    while queue:
        q = queue.popleft()
        qx,qy = q[0],q[1]

        direct = ((-1, 0), (0, -1), (0, 1), (1, 0))

        for i in range(4):
            x = qx + direct[i][0]
            y = qy + direct[i][1]
            if 0 <= x < n and 0 <= y < n and (maps[x][y] != 2 or maps[tx][ty] == 2 ) and visited[x][y] == False:
                if x == tx and y == ty:
                    return qx,qy # 이 좌표로 이동
                visited[x][y] = True
                queue.append([x,y])

    return -1




# [1] 본인이 가고싶은 편의점을 향해 최단거리로 이동 상 좌 우 하
def move_conv():
    global man, base_camp
    tmp_maps = []
    tmp_base = []
    for idx in man:
        if arrive[idx] == 0:
            if len(man[idx]) == 4:
                # 편의점 cx,cy 현재위치 mx,my
                cx, cy = man[idx][0], man[idx][1]  # 편의점 방향
                mx, my = man[idx][2], man[idx][3]  # 내 현재 위치

                nmx,nmy = bfs(cx,cy,mx,my)
                # [2] 편의점에 도착한다면 해당 편의점에서 멈추게되고,
                #     다른 사람들은 해당 편의점 칸에 못지나감.
                #     격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐
                if nmx == cx and nmy == cy:
                    tmp_maps.append([cx,cy])
                    arrive[idx] = 1
                else:
                    man[idx][2],man[idx][3] = nmx, nmy

            # [3] 현재 시간이 t <= m 이라면
            if time == idx:
                tmp = move_base(idx)

                if tmp:
                    tmp_base.append(tmp)
            #     t번 사람은 자신이 가고싶은 편의점과 가장 가까운 베이스캠프에 감
            #     (1과같은 최단거리, 시간소요 X)
    base_camp = [base_camp[i] for i in range(len(base_camp)) if base_camp[i] not in tmp_base]
    return tmp_maps + tmp_base


# [3-1] 베이스 캠프 여러개면 행 작은, 열작은 순
def move_base(idx):
    global man
    MIN = float('inf')
    MIN_point = []
    # 가고싶은 편의점과 가장 가까운 베이스캠프로 이동한다.
    if base_camp:
        cx, cy = man[idx][0], man[idx][1]
        for i in range(len(base_camp)):
            x, y = base_camp[i][0], base_camp[i][1]
            dist = abs(cx - x) + abs(cy - y)
            if MIN > dist:
                MIN = dist
                MIN_point = [x, y]
            elif MIN == dist and MIN_point[0] > x:
                MIN_point = [x, y]
            elif MIN == dist and MIN_point[0] == x and MIN_point[1] > y:
                MIN_point = [x, y]
                base_idx = idx
        if len(man[idx]) == 2:
            man[idx].extend(MIN_point)  # man[idx][2],man[idx][3] 으로 현재 위치 관리
        else:
            man[idx][2] = MIN_point[0]
            man[idx][3] = MIN_point[1]

    return MIN_point


# 모든 사람이 편의점에 도착하는 시간을 출력

arrive = [0] * (m + 1)
arrive[0] = 1

time = 1
base_camp = []
# 처음에는 3부터 시작
for i in range(n):
    for j in range(n):
        if maps[i][j] == 1:
            base_camp.append([i, j])  # 갈 수 잇는 베이스캠프
while True:
    visited_site = move_conv()  # 가까운 편의점으로 이동
    if visited_site:
        for x, y in visited_site:
            maps[x][y] = 2  # 턴 종료 후에 못가는 위치 업데이트
    if arrive.count(0) == 0:
        break
    time += 1

print(time)

내 위치에서 목표 편의점까지의 최단 거리를 구하면서 이동

-> 편의점에서 내 위치로 이동하는 경로를 구함

-> 이유? 최단 경로를 구하면서 내가 다음에 이동할 방향을 정하기 위해서

 

또, 최단경로 구할때 최단 경로만 구했다고 끝나는게 아니라 행값, 열값 작은거로 업데이트 해서 풀어줘야한다.

from collections import deque

n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
man = {i + 1: list(map(int, input().split())) for i in range(m)}
# 2면 못지나가는 베이스캠프, 편의점 (위치)
for i in man:
    man[i][0] -= 1
    man[i][1] -= 1

# TODO: 해당 턴 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐에 유의합니다.
# 사람들은 동일한 칸에 있을 수 있음
# 사람들이 목표하는 편의점은 모두 다름
# 1분 동안 1,2,3 순서로 진행
def bfs(sx,sy,tx,ty):
    queue = deque([[sx,sy,0]])
    visited = [[False]*n for _ in range(n)]
    visited[sx][sy] = True
    MIN = float('inf')
    MIN_point = []
    # 최단경로를 구하는거지, 거리가 가까운 방향으로 이동만 하는게 답은 아님
    while queue:
        q = queue.popleft()
        qx,qy,cnt = q[0],q[1],q[2]

        direct = ((-1, 0), (0, -1), (0, 1), (1, 0))

        for i in range(4):
            x = qx + direct[i][0]
            y = qy + direct[i][1]
            if 0 <= x < n and 0 <= y < n and (maps[x][y] != 2 or maps[tx][ty] == 2 ) and visited[x][y] == False:
                if x == tx and y == ty:
                    if MIN > cnt + 1:
                        MIN = cnt + 1
                        MIN_point = [qx, qy]
                    if MIN == cnt:
                        if MIN_point[0] > qx:
                            MIN_point == [qx, qy]
                        elif MIN_point[0] == x and MIN_point[1] > qy:
                            MIN_point == [qx, qy]

                if cnt > MIN:
                    continue
                visited[x][y] = True
                queue.append([x, y, cnt + 1])


    return MIN_point

# [1] 본인이 가고싶은 편의점을 향해 최단거리로 이동 상 좌 우 하
def move_conv():
    global man, base_camp
    tmp_maps = []
    tmp_base = []
    for idx in man:
        if arrive[idx] == 0:
            if len(man[idx]) == 4:
                # 편의점 cx,cy 현재위치 mx,my
                cx, cy = man[idx][0], man[idx][1]  # 편의점 방향
                mx, my = man[idx][2], man[idx][3]  # 내 현재 위치
                nmx,nmy = bfs(cx,cy,mx,my)
                # [2] 편의점에 도착한다면 해당 편의점에서 멈추게되고,
                #     다른 사람들은 해당 편의점 칸에 못지나감.
                #     격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐
                if nmx == cx and nmy == cy:
                    # tmp_maps.append([cx,cy])
                    maps[cx][cy] = 2
                    arrive[idx] = 1
                else:
                    man[idx][2],man[idx][3] = nmx, nmy

            # [3] 현재 시간이 t <= m 이라면
            if time == idx:
                tmp = move_base(idx)
                man[idx]+=tmp
                maps[tmp[0]][tmp[1]] = 2
                # tmp_maps.append(tmp)
            #     t번 사람은 자신이 가고싶은 편의점과 가장 가까운 베이스캠프에 감
            #     (1과같은 최단거리, 시간소요 X)

    return tmp_maps


# [3-1] 베이스 캠프 여러개면 행 작은, 열작은 순
def move_base(idx):
    sx,sy = man[idx][0], man[idx][1]
    # 가고싶은 편의점과 가장 가까운 베이스캠프로 이동한다.
    base_camp = []
    visited = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if maps[i][j] == 1:
                base_camp.append([i,j])
                visited[i][j] == True

    queue = deque([[sx,sy,0]])
    MIN = float('inf')
    MIN_point = []
    # 최단경로를 구하는거지, 거리가 가까운 방향으로 이동만 하는게 답은 아님
    while queue :
        q = queue.popleft()
        qx,qy,cnt = q[0],q[1],q[2]
        direct = ((-1, 0), (0, -1), (0, 1), (1, 0))
        for i in range(4):
            x = qx + direct[i][0]
            y = qy + direct[i][1]
            if 0 <= x < n and 0 <= y < n and maps[x][y] != 2 and visited[x][y] == False:
                if [x,y] in base_camp:
                    if MIN > cnt + 1:
                        MIN = cnt + 1
                        MIN_point = [x,y]
                    if MIN == cnt:
                        if MIN_point[0] > x:
                            MIN_point == [x,y]
                        elif MIN_point[0] == x and MIN_point[1] > y:
                            MIN_point == [x, y]

                if cnt > MIN:
                    continue
                visited[x][y] = True
                queue.append([x,y,cnt + 1])

    return MIN_point
# 모든 사람이 편의점에 도착하는 시간을 출력

arrive = [0] * (m + 1)
arrive[0] = 1

time = 1

while True:
    visited_site = move_conv()  # 가까운 편의점으로 이동
    if visited_site:
        for x, y in visited_site:
            maps[x][y] = 2  # 턴 종료 후에 못가는 위치 업데이트
    if arrive.count(0) == 0:
        break
    time += 1

print(time)

 

코테가 얼마 안남은 관계로 그냥 맞았다고 합리화 하기로했다(?)

시간 더있었으면 bfs 도 함수로 통일해서 썼을듯

고수 있으시면 왜 틀렸는지 말해주시길...ㅎ

 

※ 알아야 할 것

- 최단경로 조건 없으면 무조건 BFS 임!!!

- 편의점 방향에서 -> 내 방향으로 오는 로직도 떠올려보자!