[소프티어] [인증평가(1차) 기출] 로봇이 지나간 경로 (파이썬)

난이도 : ★★★☆☆

 

https://softeer.ai/practice/info.do?idx=1&eid=577 

Softeer

 

📄 문제

• 로봇은 오른쪽(동), 왼쪽(서), 아래(남), 위(북) 중 한 방향을 바라본다.
• L: 로봇이 왼쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
• R: 로봇이 오른쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
• A: 로봇이 바라보는 방향으로 두 칸 전진한다.
• ★로봇이 같은 칸을 두 번 이상 방문하지 않도록 명령한다.
• 방문했다면 '#'이고, 방문하지 않았다면 '.'로 표시한다.

 

로봇이 지도에 사수가 표시한 모든 칸들만을 방문하여 아래 정보를 계산해 주는 프로그램을 작성하려고 한다.

1. 처음 로봇을 어떤 칸에, 어떤 방향(동서남북 중 하나)으로 두어야 하는가?
2. 이후 로봇에 어떤 명령어를 어떤 순서대로 입력해야 하는가? (명령어의 개수를 최소화)

처음 로봇을 어디에, 어느 방향으로 놓는지에 따라서도 필요한 명령어 개수가 달라질 수 있음에 유의하라.

 

---

💡 아이디어

• 로봇이 같은 칸을 두 번 이상 방문하지 않으므로 출입구가 1개씩만 존재한다.
  • 즉, 출입구가 서로 바뀌어 시작 경로가 2개 존재한다. (입구- 출구, 출구 - 입구)

 

• 로봇이 2칸씩 전진하기 때문에 맞닿을 수 없다.
  • 즉, 시작점 주변에 '#'은 1개다.

 

• 시작점을 찾는 함수가 필요하다.
  
  1. 지도를 탐색해서 '#' 찾는다.
  2. '#'을 기준으로 동서남북 4방향 탐색을 시행한다.
  3. 주변에 '#'이 1개만 존재할 경우 시작점으로 지정한다.
• 입력할 명령어를 찾는 함수가 필요하다.
  1. 입력된 명령어 순서대로 출력되어야 하기 때문에 deque를 활용하여 bfs 탐색을 한다.
  2. visited로 방문 체크를 하며 지나온 곳을 표시한다.
  3. 현재 위치에서 방문 안 한 곳 중 동서남북 4방향 탐색으로 갈 수 있는 방향을 찾는다.
  4. 찾은 방향이 같은 방향인지, 회전한 방향인지 찾는다.
  5. 가능한 명령어를 deq에 넣고 다음 명령어를 찾는다.

---

 

"입력할 명령어를 찾는 함수가 필요하다."에 대해 두 가지 탐색 방법이 존재한다.

🟩 첫 번째 아이디어 (A, L, R 명령어 탐색)

• bfs를 활용하여 A, L, R 명령어로 탐색한다.
• 직진, 왼쪽, 오른쪽 회전을 차례대로 시행하여 deq에 넣는다.
• 회전할 때, deq에 넣은 다음에 직진이 가능한지 탐색하므로 회전을 어떻게 하느냐에 따라서 명령어의 개수가 달라진다.
• 마지막 위치에 도착했다는 표시가 없으면 마지막 위치에 도착했더라도 회전이 반복될 수 있다.
• 마지막 위치에 도착했다는 표시를 추가로 구현해줘야 한다.
• 명령어로 탐색하기 때문에 불필요한 회전 명령어도 탐색해야 하는 경우가 생겨 비효율적이다.

 

첫 번째 아이디어를 개선하기 위해 두 번째 아이디어를  사용한다.

✅ 두 번째 아이디어 (동서남북 4방향 탐색) - 최종코드 

• bfs를 활용하여 현재 위치를 기준으로 동서남북 4방향 탐색을 한다.
• 4방향 탐색을 통해 방문 안 한 곳 중 이동 가능한 방향을 찾는다.
• 현재 방향과 이동 가능한 방향을 비교하여 오른쪽, 왼쪽 중 회전해야 하는 방향을 찾는다.
• 변경된 위치 또는 방향, 명령어를 함께 deq에 넣는다.
• deq에 들어온 순서대로 명령어를 출력한다.
• 이동 가능한 영역만 순서대로 탐색하기 때문에 더 효율적이다.

 

반응형

 

📝 문제 풀이 (Code)

최종 코드 ( 실행시간110ms, 메모리37.45Mb )

import sys
from collections import deque

# 명령어 찾기
def bfs(i, j, d):

    visited[i][j] = 1
    deq = deque()
    # 현재 행, 열, 방향, 명령어
    deq.append((i, j, d, ''))

    while deq:
        i, j, d, order = deq.popleft()
        
		# 명령어 순서대로 출력
        print(order, end='')

        # 해당 자리에서 갈 수 있는 방향 탐색
        for newD in range(4):
            ni = i + di[newD]
            nj = j + dj[newD]
            if 0 <= ni < h and 0 <= nj < w and borad[ni][nj] == '#' and not visited[ni][nj]:
                
                if newD == d:
                	# 2칸 전진
                    ni2 = i + di[newD] *2
                    nj2 = j + dj[newD] *2

                    visited[ni][nj] = 1
                    visited[ni2][nj2] = 1

                    deq.append((ni2, nj2, d, 'A'))

                elif newD == (d-1)%4:
                	# 왼쪽 회전
                    deq.append((i, j, (d-1)%4, 'L'))
                    
                else:
                	# 오른쪽 회전
                    deq.append((i, j, (d+1)%4, 'R'))


# 시작점인지 판단하기
def isStartPoint(i,j):
    cnt = 0

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni < h and 0 <= nj < w and borad[ni][nj] == '#':
            cnt += 1
            dire = k
            
    if cnt == 1:
        return dire
    else:
        return 5

h, w = map(int, input().split())

# 방문했다면 '#'이고, 방문하지 않았다면 '.'
borad = [input() for _ in range(h)]

# 우하좌상
di = [0,1,0,-1]
dj = [1,0,-1,0]
direction = ['>', 'v', '<', '^']
# 방문체크
visited = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):

        if borad[i][j] == '#':               
            # 시작점이 될 수 있는 지 판단
            startD = isStartPoint(i,j)
            # 시작점 이면
            if startD != 5:
                print(i+1, j+1)
                print(direction[startD])
                bfs(i, j, startD)
                exit()

---

처음 코드 ( 실행시간 124ms, 메모리 37.53Mb )

최종 코드에 비해 비효율적이다. (필요한 과정이 더 많다.)

• bfs안에서 동서남북 4방향 탐색이 아닌 ['A', 'L', 'R'] 명령어로 탐색한다.
• 따라서, 직진과 회전을 반복해서 전진 가능한 경로를 탐색한다.
• 회전을 어떻게 하냐에 따라서 명령어의 개수가 달라진다.
• 마지막 위치에 도착하더라도 회전이 반복될 수 있다.
  • 이동 가능한 경로의 개수를 따로 저장 ( passRoad )
  • 탐색하면서 지나온 경로의 개수를 저장 ( visited[i][j] )
  • 이동가능한 경로 수와 이동한 경로 수가 같아지면 탐색 종료 ( passRoad == visited[i][j] )

• 명령어를 각각 deque에 같이 저장해 탐색이 종료되면 return 한다.

import sys
from collections import deque

# 명령어 찾기
def bfs(i, j, d):

    visited[i][j] = 1
    deq = deque()
    # 현재 행, 열, 방향, 현재까지 명령어, 이전 명령어
    deq.append((i, j, d, '', ''))

    while deq:
        i, j, d, order, pre = deq.popleft()
		
        # 모든 경로를 방문
        if passRoad == visited[i][j]:
            return order
        
        for now in ['A','L','R']:

            if now == 'A':
                # 로봇이 바라보는 방향으로 두 칸 전진한다.
                ni1 = i + di[d]
                nj1 = j + dj[d]
                
                ni2 = i + di[d]*2
                nj2 = j + dj[d]*2

                if 0 <= ni2 < h and 0 <= nj2 < w and borad[ni1][nj1] == '#' and not visited[ni1][nj1]:
                    visited[ni1][nj1] = visited[i][j] + 1
                    visited[ni2][nj2] = visited[i][j] + 2

                    deq.append((ni2, nj2, d, order+now, now))
            
            elif now == 'L' and pre != 'R':
            	# 왼쪽 회전
                deq.append((i, j, (d-1)%4, order+now, now))

            elif now == 'R' and pre != 'L':
            	# 오른쪽 회전
                deq.append((i, j, (d+1)%4, order+now, now))


# 시작점인지 판단하기
def isStartPoint(i,j):
    cnt = 0

    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni < h and 0 <= nj < w and borad[ni][nj] == '#':
            cnt += 1
            dire = k
            
    if cnt == 1:
        return dire
    else:
        return 5


h, w = map(int, input().split())

# 방문했다면 '#'이고, 방문하지 않았다면 '.'
borad = []
# 방문 가능한 경로 수 저장 
passRoad = 0
for _ in range(h):
    arr = input() 
    borad.append(arr)
    passRoad += arr.count('#')

# 우하좌상
di = [0,1,0,-1]
dj = [1,0,-1,0]
direction = ['>', 'v', '<', '^']
# 방문체크
visited = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):

        if borad[i][j] == '#':
                        
            # 시작점이 될 수 있는 지 판단
            startD = isStartPoint(i,j)
            # 시작점 이면
            if startD != 5:
                order = bfs(i, j, startD)
                print(i+1, j+1)
                print(direction[startD])
                print(order)
                exit()