[소프티어 6275번] 로봇이 지나간 경로(HSAT 1회 정기 코딩 인증평가 기출)

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

import sys

input = sys.stdin.readline

dx, dy = [-1,1,0,0], [0,0,-1,1]

# L : 왼쪽으로 90도 회전
# R : 오른쪽으로 90도 회전
# A : 로봇이 바라보는 방향으로 2칸 전진(범위를 벗어나면 수행X)

# 같은 칸을 2번 이상 방문하지 못하도록 명령
# 출발지점을 포함한 로봇이 방문한 모든 칸을 지도에 표시

# 로봇이 지도에 사수에 표시한 모든 칸들만을 방문하도록 조작
# 1. 처음 로봇을 어떤 칸에, 어떤 방향으로 두어야 하는가 ?
# 2. 이후 로봇에 어떤 명령어를 순서대로 입력해야 하는가 ?

# 입력하는 명령어의 개수를 최소화 했을때 [첫번째 로봇의 위치 좌표], [방향], [명령어]

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

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

start_list = []

command_count = float("inf")

for i in range(h):
    for j in range(w):
        if area[i][j] == '#':
            if 0 <= j-1 < w and area[i][j-1] == '#':   
                start_list.append((i,j,'<'))
            if 0 <= j+1 < w and area[i][j+1] == '#':
                start_list.append((i,j,'>'))
            if 0 <= i-1 < h and area[i-1][j] == '#':
                start_list.append((i,j,'^'))
            if 0 <= i+1 < h and area[i+1][j] == '#':
                start_list.append((i,j,'v'))

# 1) 왼쪽으로 돌고 2칸 전진
# 2) 오른쪽으로 돌고 2칸 전진
# 3) 왼쪽으로 두번 돌고 2칸 전진
# 4) 현재 방향에서 2칸 전진

def check_all_visited(area):

    for i in range(h):
        for j in range(w):
            if area[i][j] == '#':
                return False
    return True

answer_x, answer_y, answer_d,answer_command = 0,0,'',''

def dfs(x,y,d,commands,first_x,first_y,first_d):

    global command_count
    global answer_x
    global answer_y
    global answer_d
    global answer_command

    area[x][y] = '.'

    if check_all_visited(area):

        length = len("".join(commands))

        if length < command_count:
            command_count = length
            answer_x, answer_y, answer_d = first_x, first_y, first_d
            answer_command = "".join(commands)
        return

    

    if 0 <= y-2 < w and area[x][y-1] == '#' and area[x][y-2] == '#':

        area[x][y-1] = '.'
        area[x][y-2] = '.'

        if d == '<':
            dfs(x,y-2,'<',commands+["A"],first_x,first_y,first_d)
        elif d == '>':
            dfs(x,y-2,'<',commands+["L","L","A"],first_x,first_y,first_d)
        elif d == '^':
            dfs(x,y-2,'<',commands+["L","A"],first_x,first_y,first_d)
        elif d == 'v':
            dfs(x,y-2,'<',commands+["R","A"],first_x,first_y,first_d)

        area[x][y-1] = '#'
        area[x][y-2] = '#'

    if 0 <= y+2 < w and area[x][y+1] == '#' and area[x][y+2] == '#':
        area[x][y+1] = '.'
        area[x][y+2] = '.'

        if d == '>':
            dfs(x,y+2,'>',commands+["A"],first_x,first_y,first_d)
        elif d == '<':
            dfs(x,y+2,'>',commands+["L","L","A"],first_x,first_y,first_d)
        elif d == '^':
            dfs(x,y+2,'>',commands+["R","A"],first_x,first_y,first_d)
        elif d == 'v':
            dfs(x,y+2,'>',commands+["L","A"],first_x,first_y,first_d)
            
        area[x][y+1] = '#'
        area[x][y+2] = '#'

    if 0 <= x-2 < h and area[x-1][y] == '#' and area[x-2][y] == '#':

        area[x-1][y] = '.'
        area[x-2][y] = '.'

        if d == '^':
            dfs(x-2,y,'^',commands+["A"],first_x,first_y,first_d)

        elif d == 'v':
            dfs(x-2,y,'^',commands+["L","L","A"],first_x,first_y,first_d)

        elif d == '<':
            dfs(x-2,y,'^',commands+["R","A"],first_x,first_y,first_d)

        elif d == '>':
            dfs(x-2,y,'^',commands+["L","A"],first_x,first_y,first_d)

        area[x-1][y] = '#'
        area[x-2][y] = '#'

    if 0 <= x+2 < h and area[x+1][y] == '#' and area[x+2][y] == '#':

        area[x+1][y] = '.'
        area[x+2][y] = '.'

        if d == 'v':
            dfs(x+2,y,'v',commands+["A"],first_x,first_y,first_d)
        elif d == '^':
            dfs(x+2,y,'v',commands +["L","L","A"],first_x,first_y,first_d)
        elif d == '<':
            dfs(x+2,y,'v',commands +["L","A"],first_x,first_y,first_d)
        elif d == '>':
            dfs(x+2,y,'v',commands +["R","A"],first_x,first_y,first_d)
        
        area[x+1][y] = '#'
        area[x+2][y] = '#'
        
    area[x][y] = '#'

for sx, sy, sd in start_list:
    dfs(sx,sy,sd,[],sx,sy,sd)

print(answer_x+1,answer_y+1)

print(answer_d)

print(answer_command)

 

이번 문제는 로봇에게 왼쪽으로 회전(L), 오른쪽으로 회전(R), 앞으로 전진(A) 이 3가지 명령이 가능하다고 했을 때, 주어진 좌표의 영역들을 최소한의 명령으로 모두 방문하기 위한 [초기 좌표], [초기 방향], [명령어] 를 구하는 문제이다.

 

처음에 이 문제를 풀 때 왼쪽이랑 오른쪽만 존재해서 헷갈렸었는데, 사실상 모든 경우의 수를 구하기 위해서는 현재 방향의 반대 방향도 탐색해보아야 한다.

 

따라서 DFS 알고리즘으로 왼쪽으로 2번 돌거나(LL), 오른쪽으로 2번 돌거나(RR) 해서 반대방향까지 탐색해주면 모든 경우의 수를 구할 수 있다.

• 왼쪽으로 회전 후 전진( L A )
• 오른쪽으로 회전 후 전진 ( R A )
• 반대편으로 회전 후 전진 ( L L A or R R A )
• 현재 방향으로 전진 ( A )

총 4가지 경우의 수로 모든 경우의 수를 탐색하였다.

 

그리고 모든 좌표가 방문되었는지 확인하는 함수(check_all_visited)를 선언하여 종료 여부를 결정하였으며 모든 좌표가 방문되었다면 여태까지 수행된 명령어들(commands)의 길이를 구한 뒤 answer를 업데이트해주었다.