[소프티어 Lv3] [HSAT 1회 정기 코딩 인증평가 기출] 로봇이 지나간 경로
로보틱스 분야는 현대자동차그룹의 미래 성장동력인 5대 신사업 중 하나이다.
현대자동차그룹에 입사하여 로봇 연구 개발 부서에 막 입사한 당신은 아래와 같은 기능을 하는 간단한 로봇의 사용법을 전달받았다. 로봇은 H행 W열의 2차원 격자판 위를 돌아다닌다. 격자판의 각 칸은 정사각형 모양이며, 로봇은 격자판의 칸 하나를 차지한다. 로봇은 오른쪽(동), 왼쪽(서), 아래(남), 위(북) 중 한 방향을 바라볼 수 있다.
로봇의 이동을 제어하는 명령어는 다음과 같이 세 가지이다.
* L: 로봇이 왼쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
* R: 로봇이 오른쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
* A: 로봇이 바라보는 방향으로 두 칸 전진한다. 단, 이 과정에서 로봇이 격자판 바깥을 나간다면 로봇은 이 명령을 수행할 수 없다.
당신의 사수는 로봇 사용법을 시연해 주고자, 격자판 어딘가에 로봇을 두고 명령어를 입력해 가며 로봇을 움직였다. 이 때, 사수는 로봇이 같은 칸을 두 번 이상 방문하지 않도록 명령을 내렸고, 로봇이 방문한 모든 칸 (출발 칸 포함)을 지도에 표시하였다. 당신은 다음 날 출근해서 사수가 한 것처럼 로봇에 명령을 내려봐야겠다고 생각하며 퇴근하였다.
다음 날 출근한 당신은 사수가 넘겨준 지도를 보고 로봇이 어떤 칸들에 방문하였는지를 정확히 알 수 있었지만, 사수가 로봇에 어떤 명령을 내렸는지는 알 수 없었다. 당신은 오늘 로봇이 지도에 사수가 표시한 모든 칸들만을 방문하도록 로봇을 조작하고자 하며, 이를 위해 아래 정보를 계산해 주는 프로그램을 작성하려고 한다.
1. 처음 로봇을 어떤 칸에, 어떤 방향(동서남북 중 하나)으로 두어야 하는가?
2. 이후 로봇에 어떤 명령어를 어떤 순서대로 입력해야 하는가?
명령어를 입력하는 일은 번거롭기 때문에, 당신은 입력할 명령어의 개수를 최소화해야 한다. 처음 로봇을 어디에, 어느 방향으로 놓는지에 따라서도 필요한 명령어 개수가 달라질 수 있음에 유의하라.
* 5 ≤ H, W ≤ 25
* 사수는 한 번 이상의 A 명령을 내렸다. 따라서, 로봇이 방문한 칸 수는 최소 3개 이상이다.
이 문제의 경우 목표를 달성할 수 있는 방안이 여러개 일 수 있으며 그 중 아무 것이나 출력해도 답으로 처리된다.
아래의 입출력 예제를 보면, 하나의 입력에 대해 각각 달성할 수 있는 방안(출력)이 2개씩 존재한다. [예제 1, 예제 2], [예제 3, 예제 4] 두 가지 방안 중 하나가 정답으로 출력된 경우 정답으로 인정된다.
첫 번째 줄에 격자판의 세로 크기 H와 가로 크기 W가 공백 하나를 사이로 두고 주어진다. 다음에는 사수가 넘겨준 지도가 주어진다. H개의 줄에 W개의 문자가 주어지는데, 이 중 i(1 ≤ i ≤ H)번째 줄의 j(1 ≤ j ≤ W)번째 문자는, 사수가 조작한 로봇이 i행 j열을 방문했다면 '#'이고, 방문하지 않았다면 '.'이다.
첫 번째 줄에 두 개의 정수 a(1 ≤ a ≤ H)와 b(1 ≤ b ≤ W)를 공백 하나씩을 사이로 두고 출력한다. 이는 처음 로봇을 격자판의 a행 b열에 두어야 함을 의미한다.
두 번째 줄에 '>', '<', 'v', '^' (따옴표 제외) 중 하나를 출력한다. 이 문자는 처음 로봇이 바라보는 방향을 의미하며, >는 동쪽, <는 서쪽, v는 남쪽, ^는 북쪽이다.
세 번째 줄에 당신이 로봇에 내려야 하는 명령어들을 공백 없이 명령을 내릴 순서대로 출력한다. 이 문자열의 길이가 곧 당신이 내리는 명령어의 개수이며, 명령어의 개수를 최소화해야 정답 처리된다.
명령어의 개수를 최소화하면서 목표를 달성할 수 있는 방법이 여러 가지라면, 그 중 한 가지를 아무거나 출력하면 된다.
5 8 #######. ........ ........ ........ ........
1 7 < AAA
5 8 #######. ........ ........ ........ ........
1 1 > AAA
9 14 .......###.... .........#.... .#####...###.. .#.........#.. .#.#####...### .#.#...#.....# .###.###.....# .....#.......# .....#########
3 6 < AALAALALARAARARALALAAAALAALARALARALA
9 14 .......###.... .........#.... .#####...###.. .#.........#.. .#.#####...### .#.#...#.....# .###.###.....# .....#.......# .....#########
1 8 > ARALARALARAARAAAARARALALAALARARAARAA
[내 풀이]
※ 소요시간 : 1시간 13분
※ 풀이 전략
- n이 25니까 완전탐색으로 하기로 결정했다. (DFS)
h, w = map(int, input().split())
mtx = [list(input()) for x in range(h)]
# 상수
# 동남서북
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
direction = ['>', 'v', '<', '^']
# 길의 개수
length = sum([row.count('#') for row in mtx])
#
def dfs(x, y, m, k):
global s
global d
global c
global mins
global mind
global minc
if k==length:
z = 0
tmpc = ''
while z<len(c)-1:
if c[z] == 'A' and c[z+1] == 'A':
tmpc += 'A'
z += 2
else:
tmpc += c[z]
z += 1
c = tmpc
if len(c) < len(minc):
mins = s
minc = c
mind = d
for i in range(4):
if k==1:
d = i
m = i
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<h and 0<=ny<w and not visited[nx][ny] and mtx[nx][ny]=='#':
tmp = ''
if -3 == i-m:
tmp += 'R'
if -2 <= i-m <0:
tmp += 'L'*(m-i)
if 0<= i-m <= 2:
tmp += 'R'*(i-m)
if 3 == i-m:
tmp += 'L'
tmp += 'A'
c += tmp
visited[nx][ny] = 1
dfs(nx, ny, i, k+1)
visited[nx][ny] = 0
c = c[:-(len(tmp))]
mins = (0,0)
mind = 0
minc = 'A'*(10**6)
for i in range(h):
for j in range(w):
if mtx[i][j] == '#':
visited = [[0]*w for _ in range(h)]
visited[i][j] = 1
s = (i,j)
c = ''
d = ''
dfs(i, j, 0, 1)
print(mins[0]+1, mins[1]+1)
print(direction[mind])
print(minc)
※ 생각 정리
- 이렇게 코드가 긴 거 맞나... 싶었지만, 실제로 길었다.
[다른 사람의 풀이]
※ 풀이 전략
- 내 풀이가 너무 긴 것 같아 다른 사람들의 풀이를 검색해봤는데 역시 길었다. 다른 사람들은 BFS(?)로 푼 경우가 많은 것 같다. BFS라기엔 한 지점에서 다른 방향으로 가는 길이 1가지 밖에 없다고 확신한 상태에서 푸시는 것 같아 BFS가 맞는 진 모르겠다.
- 사실 테스트 케이스가 많았다면 길이 꼬불꼬불 겹쳐있을 수도 있어서 이 경우에는 한 붓 그리기는 가능해도 가능한 경로가 하나라고는 볼 수 없게 되는데, 이 경우에서는 오류가 나는 것이 아닌가? 그래서 실제로 테스트 해봤다. 그런데 역시 이런 풀이들은 다 내가 생각했던 반례를 통과하지 못한다.
(예를 들면 이런 형태)
그런데 실제로 아래 코드를 돌려보면
이렇게 경로가 고장나는 걸 확인할 수 있었다. AARLR 까지만 확인해도 잘못된 걸 확인할 수 있었다. 우회전, 좌회전을 하면 제자리 걸음인데 RL 을 연이어서 할 필요가 없기 때문이다.
import sys
from collections import deque # BFS면 deque
# 먼저 '#'을 다 잇는다
# 다 이은 최적 루트는 2가지 경우 밖에 없다.
# 그 중 한 가지를 아무거나 출력하면 된다.
# 상하좌우 조합
dx = [-1,0,1,0]
dy = [0,1,0,-1]
directions = ['^','>','v','<']
def check(x,y):
cnt = 0
for i in range(4): # 상하좌우 4개
xx=x+dx[i]
yy=y+dy[i] # 상하좌우 좌표 업데이트
# 업데이트 된 좌표가 격자판을 넘지 않으며 4방향중 다음 위치가 '#'이 있는 위치일때만
if 0<=xx<H and 0<=yy<W and maps[xx][yy]=='#':
start = directions[i] # 시작할때 어디를 보고 시작하는 지 방향 체크
cnt+=1
if cnt>1: # 꺽이는 부분이면
return False
return start
def BFS(x,y):
path = []
Q = deque()
Q.append((x,y))
visited[x][y] = True # 일단 방문 체크
while Q: # 한쪽 방향 끝날때 까지
tmp=Q.popleft() # 시작 위치 좌표 꺼내
for i in range(4): # 4방향 확인
xx=tmp[0]+dx[i] # 거기에 좌표 업데이트 값
yy=tmp[1]+dy[i]
direction=directions[i] # 그때 방향, 4방향 확인
# 격자판 안에서 '#'이면서 한번도 방문한적없으면
if 0<=xx<H and 0<=yy<W and maps[xx][yy]=='#' and visited[xx][yy]==False:
visited[xx][yy] = True # 방문 체크
path.append(direction) # 방향
Q.append((xx,yy)) # 좌표
# -> 4방향을 다 살피며
return deque(path) # '#'을 다 이어서
if __name__=="__main__":
H, W = map(int, sys.stdin.readline().split()) # 격자판 만들기
maps = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
# sys.stdin = open('input.txt', 'r')
# H,W=map(int, input().split())
# maps = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
visited = [[False] * W for _ in range(H)] # 방문 표 만들기
ans = []
for row in range(H):
for col in range(W): # 행, 열 탐색
if maps[row][col]=='#' and check(row,col): # '#'인 경우이자 직선방향이면
trace=BFS(row,col) # 갈 수 있는 최적의 루트가 나온다.
print(row+1, col+1) # 시작 위치
# print(trace) # 그때 방향들
print(trace[0]) # 첫 방향
# 이때 시작 위치의 로봇 방향
current = trace.popleft()
cnt = 1
# 명령어 출력을 위해
for next in trace:
if current == next:
cnt += 1
current = next
if cnt % 2 == 0: # 방향이 2개씩 되어있으면
ans.append("A") # 이동 명령어 'A'
cnt = 0
else: # 그다음 방향이 현재 방향과 일지 하지 않으면 회전인데
# 왼쪽이냐 오른쪽이냐
if directions[directions.index(current) - 1] == next:
ans.append("L")
else:
ans.append("R")
current = next # 회전수행 후 방향이 바뀐다.
cnt = 1
for i in ans:
print(i, end="")
# 찾으면 더 수행 할 필요없이 프로그램 끝내기
sys.exit(0)
중요 포인트
- 그런데 구현 방법 중에, 처음부터 AARL이렇게 적지 않고 >>^>^^ 이런 식으로 이동하는 경로를 먼저 기록한 다음에 나중에 경로를 보고 >>이면 A, >^이면 회전이므로 L또는 R 이런 식으로 결정할 수도 있던 건 새로운 관점이었던 것 같아서, 나중에 활용해봐야겠다고 생각했다.
'알고리즘 문제풀이 > 소프티어' 카테고리의 다른 글
| [소프티어 Lv3] [HSAT 3회 정기 코딩 인증평가 기출] 플레이페어 암호 (1) | 2023.11.03 |
|---|---|
| [소프티어 Lv2] 장애물 인식 프로그램(DFS, BFS) (1) | 2023.11.03 |
| [소프티어 Lv3] 스마트 물류(구현) (0) | 2023.11.02 |
| [소프티어 Lv2] 지도 자동 구축(DP) (0) | 2023.11.02 |
| [소프티어 Lv2] [21년 재직자 대회 예선] 회의실 예약(문자열 포맷) (1) | 2023.11.02 |
댓글