HSAT 1회 기출 - 로봇이 지나간 경로

HSAT 1회 정기 코딩 인증 평가 기출 문제 중 "로봇이 지나간 경로" 문제를 풀이하고 있습니다.

 

 HSAT 1회 기출 - 로봇이 지나간 경로

 

로봇이 지나간 경로

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 풀면서 헷갈렸던 요구 사항에 대해서 작성해보자면, 다음과 같다
• 로봇은 같은 칸을 두 번 방문하지 않으며, 한 번 이동할 때 2칸을 이동하기 때문에 로봇의 이동 경로에 싸이클이 형성될 수 없다.
  • 출발 칸과 그 주변 칸을 밟을 수가 없다!
• 최초에 로봇이 바라보는 방향에 따라 명령어 수가 한 개 늘어날 수 있다.
  • 예를 들어, 이동 경로는 오른쪽인데 로봇이 아래를 바라본다면 제일 처음 로봇의 방향을 바꾸는 명령어를 실행해야 한다.
  • 최소 명령어 수를 구해야 하기 때문에 로봇은 시작할 때 이동 경로를 바라보고 있으면 된다.
• 앞서 말했던 조건으로 인해서 로봇의 시작 지점은 두 점 중에 하나이다.
  • 경로의 시작점과 끝점
• 경로의 시작점과 끝점을 어떻게 구할 수 있을까?
  • 아주 간단한데 인접한 칸에 "#"이 한 개만 존재하는 칸이 시작점 혹은 끝점이다.
• 그러면 두 개의 점에서 BFS를 돌려서 풀 수 있다.
• 이때 주의해야할 점은 다음과 같다.
  • 로봇의 다음 이동 방향이 현재 방향과 다르면, 방향을 바꾸는 커맨드를 섞는다.
  • BFS 탐색 시에 로봇이 두 칸을 이동한다는 점을 고려해서 현재 위치에서 두 칸 떨어진 인접 점들을 방문했는지 아닌지를 체크할 가능성이 크다.
  • 하지만, 두 칸 떨어진 점이 이동 경로의 한 점이지만 그 점과 현재 점 사이에 존재하는 칸이 로봇의 이동 경로에 포함되지 않는 경우가 발생할 수 있기 때문에 BFS로 다음 이동할 곳을 탐색할 때에 꼭 두 칸 떨어진 점과 한 칸 떨어진 점을 같이 체킹해야 한다.
• 이 조건들을 가지고 코드로 구현하면 아래와 같다.

코드

import sys
from collections import deque
import copy

def isInTheMap(x, y):
    global H, W
    if x > -1 and x < H and y > -1 and y < W:
        return True
    return False

# 아래, 오른, 위, 왼
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
dir = ["v", ">", "^", "<"]

H, W = map(int, sys.stdin.readline().split(" "))

map = list()

for row in range(H):
    line = list(sys.stdin.readline().strip())
    map.append(line)

startPoint = list()

for row in range(H):
    for col in range(W):
        if map[row][col] == '#':
            adj = 0
            for i in range(4):
                if isInTheMap(row+dx[i], col+dy[i]) and map[row+dx[i]][col+dy[i]] == '#':
                    adj += 1
            if adj == 1:
                startPoint.append([row, col])

answerStartPoint = list()
answerDirection = ""
lenCommands = 25*25
answerCommands = list()

for point in startPoint:
    direction = -1
    # 1단계 로봇의 시작 방향을 찾는다.
    for i in range(4):
        if isInTheMap(point[0]+dx[i], point[1]+dy[i]) and map[point[0]+dx[i]][point[1]+dy[i]] == '#':
            direction = i

    # Visit 배열을 만든다
    visited = [[False for _ in range(W)] for _ in range(H)]

    # Queue 생성
    q = deque()
    q.append([point[0], point[1], direction])

    commands = list()

    # BFS
    while q:
        data = q.popleft()
        cx = data[0]
        cy = data[1]
        d = data[2]

        if visited[cx][cy]:
            continue

        visited[cx][cy] = True

        canMove = [d, (d-1) % 4, (d+1) % 4]
        c = ['A', 'R', 'L']

        for idx, j in enumerate(canMove):
            nx_1 = cx + dx[j]
            ny_1 = cy + dy[j]
            
            nx_2 = cx + dx[j] * 2
            ny_2 = cy + dy[j] * 2
            if isInTheMap(nx_2, ny_2) and map[nx_1][ny_1] == '#' and map[nx_2][ny_2] == '#':
                if d != j:
                    commands.append(c[idx])
                commands.append("A")
                q.append([nx_2, ny_2, j])
                break
    if len(commands) < lenCommands:
        answerStartPoint = copy.deepcopy(point)
        answerDirection = dir[direction]
        answerCommands = copy.deepcopy(commands)
        lenCommands = len(commands)
print(f"{answerStartPoint[0] + 1} {answerStartPoint[1] + 1}")
print(answerDirection)
print("".join(answerCommands))

 

1시간 30분 정도 소요되었던 것 같다. 1회차 때에는 구현에 가까운 것들을 시킨 것을 알 수 있었다.

 

추천글

https://softeer.ai/class/devcrew/study/resource/detail/description/6275?id=245&resourceId=282

Softeer - 현대자동차그룹 SW인재확보플랫폼