[틀림][Softeer][level3][인증평가(1차) 기출] 로봇이 지나간 경로

 

 

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

Softeer

 

 

문제

 

로보틱스 분야는 현대자동차그룹의 미래 성장동력인 5대 신사업 중 하나이다.

현대자동차그룹에 입사하여 로봇 연구 개발 부서에 막 입사한 당신은 아래와 같은 기능을 하는 간단한 로봇의 사용법을 전달받았다. 로봇은 H행 W열의 2차원 격자판 위를 돌아다닌다. 격자판의 각 칸은 정사각형 모양이며, 로봇은 격자판의 칸 하나를 차지한다. 로봇은 오른쪽(동), 왼쪽(서), 아래(남), 위(북) 중 한 방향을 바라볼 수 있다.

로봇의 이동을 제어하는 명령어는 다음과 같이 세 가지이다.

* L: 로봇이 왼쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
* R: 로봇이 오른쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
* A: 로봇이 바라보는 방향으로 두 칸 전진한다. 단, 이 과정에서 로봇이 격자판 바깥을 나간다면 로봇은 이 명령을 수행할 수 없다.

당신의 사수는 로봇 사용법을 시연해 주고자, 격자판 어딘가에 로봇을 두고 명령어를 입력해 가며 로봇을 움직였다. 이 때, 사수는 로봇이 같은 칸을 두 번 이상 방문하지 않도록 명령을 내렸고, 로봇이 방문한 모든 칸 (출발 칸 포함)을 지도에 표시하였다. 당신은 다음 날 출근해서 사수가 한 것처럼 로봇에 명령을 내려봐야겠다고 생각하며 퇴근하였다.

다음 날 출근한 당신은 사수가 넘겨준 지도를 보고 로봇이 어떤 칸들에 방문하였는지를 정확히 알 수 있었지만, 사수가 로봇에 어떤 명령을 내렸는지는 알 수 없었다. 당신은 오늘 로봇이 지도에 사수가 표시한 모든 칸들만을 방문하도록 로봇을 조작하고자 하며, 이를 위해 아래 정보를 계산해 주는 프로그램을 작성하려고 한다.

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

명령어를 입력하는 일은 번거롭기 때문에, 당신은 입력할 명령어의 개수를 최소화해야 한다. 처음 로봇을 어디에, 어느 방향으로 놓는지에 따라서도 필요한 명령어 개수가 달라질 수 있음에 유의하라.

 

 

 

💻  1차 :  틀린코드 ---- 10점  ---- (23.02.08)

 

급하게 제출하지 마라 지은아 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ제발,...

집 빨리가고 싶은건 알겠는데... 최대한 꼼꼼히 봐,.....

 

 

 

뭐가 문제인지 보니까.. 중간에 A를 추가하는 로직이 빠진것같다.

 

import sys
import copy
from collections import deque

h, w = map(int,sys.stdin.readline().split())

d = [[0,1],[-1,0],[0,-1],[1,0]]
str_d = ['>','^','<','v']


COMMAND_MOVE = 'A'
COMMAND_TURN_LEFT = 'L'
COMMAND_TURN_RIGHT = 'R'


def bfs(x,y):
    
    graph = copy.deepcopy(input_graph)

    visited = [[False] * w for _ in range(h)]
    queue = deque()
    queue.append([x,y])
    visited[x][y] = True
    graph[x][y] = '.'
    moving = False

    save_start_dir = []
    save_command = []

    pre_dir = 0
    while queue:
        
        r,c = queue.popleft()
        check4Dir = 0

        for now_dir in range(4):
            check4Dir += 1
            dr = r + d[now_dir][0]*2
            dc = c + d[now_dir][1]*2
            
            if(0>dr or dr>=h or 0 > dc or dc >= w):
                continue

            path_r = dr - d[now_dir][0]
            path_c = dc - d[now_dir][1]
            
            #경로가 아니면 바로 다음 방향 체크하기 위함
            if (graph[dr][dc] != '#' or graph[path_r][path_c] != '#'):
                continue
            
            if not visited[dr][dc] and not visited[path_r][path_c]: #방문 안해서 움직이기 가능
                
                #---- 01) 정보 저장 ----
                if not moving: #첫 움직임일때 저장할 정보들
                    moving = True
                    save_start_dir = [ r, c, str_d[now_dir] ]
                    save_command.append(COMMAND_MOVE)
                    
                else: #이미 어딘가에서 출발한 상황에 저장할 정보들
                    #now_dir는 움직이려는 방향, 이전의 방향(save_pre_dir)과 비교해주기 
                    if pre_dir == now_dir :
                        save_command.append(COMMAND_MOVE)
                    elif pre_dir == 0 and now_dir == 3:
                        save_command.append(COMMAND_TURN_RIGHT)
                    elif pre_dir == 3 and now_dir == 0:
                        save_command.append(COMMAND_TURN_LEFT)
                    elif pre_dir == now_dir - 1 :
                        save_command.append(COMMAND_TURN_LEFT) 
                    elif pre_dir == now_dir + 1 :
                        save_command.append(COMMAND_TURN_RIGHT) 


                #---- 02) 움직이기 ----                
                visited[dr][dc], visited[path_r][path_c] = True, True
                graph[dr][dc], graph[path_r][path_c] = '.', '.'
                queue.append([dr,dc])
                pre_dir = now_dir
                



    #while 탈출 후 #이 없으면 -- 이 경로를 리턴하고
    #있으면 return
    for r in graph:
        if '#' in r :
            return 

    
    #save_start_dir = [r,c, str_d[now_dir] ]
    print(save_start_dir[0]+1,save_start_dir[1]+1)
    print(save_start_dir[2])
    print(''.join(save_command))
    
    exit()
            


    
input_graph = [list(map(str, input())) for _ in range(h) ] 
'''
print("-----------")
print(input_graph)
print("-----------")
'''

for i in range(h):
    for j in range(w):
        if input_graph[i][j] == '#':
            bfs(i,j)

 

 

💻  2차 :  오답 비율은 줄었으나 여전히 10점이다...(23.02.08)

왜지? 애초에 최소방법만 들어갈 수 있게 해서 로직상 문제는 없는것 같은데...

내일 다시 풀어봐야 할것 같다.

import sys
import copy
from collections import deque

h, w = map(int,sys.stdin.readline().split())

d = [[0,1],[-1,0],[0,-1],[1,0]]
str_d = ['>','^','<','v']


COMMAND_MOVE = 'A'
COMMAND_TURN_LEFT = 'L'
COMMAND_TURN_RIGHT = 'R'


def bfs(x,y):
    
    graph = copy.deepcopy(input_graph)

    visited = [[False] * w for _ in range(h)]
    queue = deque()
    queue.append([x,y])
    visited[x][y] = True
    graph[x][y] = '.'
    moving = False

    save_start_dir = []
    save_command = []

    pre_dir = 0
    while queue:
        
        r,c = queue.popleft()
        check4Dir = 0

        for now_dir in range(4):
            check4Dir += 1
            dr = r + d[now_dir][0]*2
            dc = c + d[now_dir][1]*2
            
            if(0>dr or dr>=h or 0 > dc or dc >= w):
                continue

            path_r = dr - d[now_dir][0]
            path_c = dc - d[now_dir][1]
            
            #경로가 아니면 바로 다음 방향 체크하기 위함
            if (graph[dr][dc] != '#' or graph[path_r][path_c] != '#'):
                continue
            
            if not visited[dr][dc] and not visited[path_r][path_c]: #방문 안해서 움직이기 가능
                
                #---- 01) 정보 저장 ----
                if not moving: #첫 움직임일때 저장할 정보들
                    moving = True
                    save_start_dir = [ r, c, str_d[now_dir] ]
                    
                else: #이미 어딘가에서 출발한 상황에 저장할 정보들
                    #now_dir는 움직이려는 방향, 이전의 방향(save_pre_dir)과 비교해주기 
                    
                    if pre_dir == 0 and now_dir == 3:
                        save_command.append(COMMAND_TURN_RIGHT)

                    elif pre_dir == 3 and now_dir == 0:
                        save_command.append(COMMAND_TURN_LEFT)

                    elif pre_dir == now_dir - 1 :
                        save_command.append(COMMAND_TURN_LEFT)

                    elif pre_dir == now_dir + 1 :
                        save_command.append(COMMAND_TURN_RIGHT)

                #---- 02) 움직이기 ----                
                save_command.append(COMMAND_MOVE)
                visited[dr][dc], visited[path_r][path_c] = True, True
                graph[dr][dc], graph[path_r][path_c] = '.', '.'
                queue.append([dr,dc])
                pre_dir = now_dir
                



    #while 탈출 후 #이 없으면 -- 이 경로를 리턴하고
    #있으면 return
    for r in graph:
        if '#' in r :
            return 

    
    #save_start_dir = [r,c, str_d[now_dir] ]
    print(save_start_dir[0]+1,save_start_dir[1]+1)
    print(save_start_dir[2])
    print(''.join(save_command))
    
    exit()
            


input_graph = [list(map(str, input())) for _ in range(h) ] 


for i in range(h):
    for j in range(w):
        if input_graph[i][j] == '#':
            bfs(i,j)