삼성 SW역량테스트 기출 / 2015 하반기 2번 문제 2개의 사탕 - BFS, 중력, 백트래킹 / Python 파이썬

 

*문제 출처는 삼성전자, 코드트리에 있습니다.

 

삼멘 6일차

벌써..?!

문제 제목: 2개의 사탕

문제 사이트: https://www.codetree.ai/training-field/frequent-problems/problems/two-candies/submissions?page=4&pageSize=20

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

 

---

처음에 BFS로 중력 방향 정하면서 해야겠다 생각하고 구현하는데,

빨간 사탕과 파란 사탕의 중력 (만약 빨간 구슬이 아래에 있으면 그 위에 파란 구슬이 있어야하는) 부분 구현할때 머리가 좀 아팠다.

 

예시로 아래의 표에서 아래 방향으로 중력이 작용한다 하자.

 

중력 작용 전

	O
	O

 

중력 작용 후 (만약 두개가 겹쳐도 된다면) 이런식으로 나올것이다.

O(움직인거리:1) O(움직인 거리:2)

	O(1) O(2)

 

하지만 사탕끼리도 '중력'이 작용해서 아래에 먼저 파란색 위에 빨간 사탕이 올것이다.

이때 우리는 빨간색 사탕이 바닥까지 하강했을때 2만큼 왔으니,

파란 사탕보다 더 뒤에 있었음을 알 수 있다.

 

그래서 온 방향에서 한칸 뒤로 보내준다. 

	O(1)
	O(1)

 

그럼 해결됨

 

회전 하면서 한 방향으로 사탕이 내려가게 하고

결국에는 뒤에 있는 애가 더 많이 움직이게 되는거니까, 많이 내려온 애가  내려온 방향으로 한칸 뒤로 가면 됨

if (rnx,rny) == (bnx,bny):
    # 더 많이 움직인 애가 뒤로 가기
    if r_dist > b_dist:
        rnx -= direct[i][0]
        rny -= direct[i][1]
    else:
        bnx -= direct[i][0]
        bny -= direct[i][1]

 

그리고 BFS로 방향 돌려가면서 중력 구현하면 끝!

 

 

회전시 다시 처음 온 좌표대로 오면 어차피 똑같은 상태트리가 그려질것이니 set으로 방문 검사를 해준다.

visited = set((red,blue)) # red, blue 좌표 저장

나의 풀이

from collections import deque

n,m = map(int,input().split())
maps = [list(map(str,input())) for _ in range(n)]
for i in range(n):
    for j in range(m):
        if maps[i][j] == 'R':
            red = (i,j)
        elif maps[i][j] == 'B':
            blue = (i,j)

def BFS():
    queue = deque([])
    queue.append((red,blue,0))
    visited = set((red,blue)) # red, blue 좌표 저장
    direct = ((1,0),(-1,0),(0,1),(0,-1))
    while queue:
        r,b,cnt = queue.popleft()
        rx, ry = r[0], r[1]
        bx, by = b[0], b[1]

        if cnt > 10 :
            return -1
        if maps[rx][ry] == 'O':
            if maps[bx][by] == 'O':
                continue
            else:
                return cnt

        for i in range(4):
            rnx, rny, r_dist = gravity(rx, ry, direct[i][0],direct[i][1])
            bnx, bny, b_dist = gravity(bx, by, direct[i][0],direct[i][1])
            if maps[bnx][bny] == 'O':
                # blue 가 먼저 가게 되는 경우는 가지치기
                continue
            if (rnx,rny) == (bnx,bny): # 빨간 구슬과 파란 구슬 위치가 겹치면
                # 더 많이 움직인 애가 뒤로 가기
                if r_dist > b_dist:
                    rnx -= direct[i][0]
                    rny -= direct[i][1]
                else:
                    bnx -= direct[i][0]
                    bny -= direct[i][1]
            if ((rnx,rny),(bnx,bny)) not in visited:
                queue.append(((rnx,rny),(bnx,bny),cnt + 1))
                visited.add(((rnx,rny),(bnx,bny)))
    return -1
# 중력
def gravity(x,y,dx,dy):
    # 박스 안에 공간이 감싸져있다는 조건으로 범위는 생략
    dist = 0
    while maps[x+dx][y+dy] != '#' and maps[x][y] != 'O': 
        # 이동하게될 거리가 벽이 아니고, 현재 위치가 구멍이 아니라면
        x += dx
        y += dy
        dist += 1
    return x,y,dist

print(BFS())

 

구현 중간중간에 있는 조건문은 결국 파란 사탕이 먼저 나가면 안되고, 빨간 사탕이 먼저 빠져나와함을 위한것임

---

※ 알아야 할 것

- 중력 구현할때 두개의 사탕의 위치가 겹치게 된다면, 많이 내려온 애를 올리면 된다.