문제
로보틱스 분야는 현대자동차그룹의 미래 성장동력인 5대 신사업 중 하나이다.
현대자동차그룹에 입사하여 로봇 연구 개발 부서에 막 입사한 당신은 아래와 같은 기능을 하는 간단한 로봇의 사용법을 전달받았다.
로봇은 H행 W열의 2차원 격자판 위를 돌아다닌다. 격자판의 각 칸은 정사각형 모양이며, 로봇은 격자판의 칸 하나를 차지한다. 로봇은 오른쪽(동), 왼쪽(서), 아래(남), 위(북) 중 한 방향을 바라볼 수 있다.
로봇의 이동을 제어하는 명령어는 다음과 같이 세 가지이다.
* L: 로봇이 왼쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
* R: 로봇이 오른쪽으로 90도 회전하며, 이에 따라 바라보는 방향이 바뀐다.
* A: 로봇이 바라보는 방향으로 두 칸 전진한다. 단, 이 과정에서 로봇이 격자판 바깥을 나간다면 로봇은 이 명령을 수행할 수 없다.
당신의 사수는 로봇 사용법을 시연해 주고자, 격자판 어딘가에 로봇을 두고 명령어를 입력해 가며 로봇을 움직였다. 이 때, 사수는 로봇이 같은 칸을 두 번 이상 방문하지 않도록 명령을 내렸고, 로봇이 방문한 모든 칸 (출발 칸 포함)을 지도에 표시하였다. 당신은 다음 날 출근해서 사수가 한 것처럼 로봇에 명령을 내려봐야겠다고 생각하며 퇴근하였다.
다음 날 출근한 당신은 사수가 넘겨준 지도를 보고 로봇이 어떤 칸들에 방문하였는지를 정확히 알 수 있었지만, 사수가 로봇에 어떤 명령을 내렸는지는 알 수 없었다. 당신은 오늘 로봇이 지도에 사수가 표시한 모든 칸들만을 방문하도록 로봇을 조작하고자 하며, 이를 위해 아래 정보를 계산해 주는 프로그램을 작성하려고 한다.
1. 처음 로봇을 어떤 칸에, 어떤 방향(동서남북 중 하나)으로 두어야 하는가?
2. 이후 로봇에 어떤 명령어를 어떤 순서대로 입력해야 하는가?
명령어를 입력하는 일은 번거롭기 때문에, 당신은 입력할 명령어의 개수를 최소화해야 한다.
처음 로봇을 어디에, 어느 방향으로 놓는지에 따라서도 필요한 명령어 개수가 달라질 수 있음에 유의하라.
제약조건
* 5 ≤ H, W ≤ 25
* 사수는 한 번 이상의 A 명령을 내렸다. 따라서, 로봇이 방문한 칸 수는 최소 3개 이상이다.
입력
첫 번째 줄에 격자판의 세로 크기 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는 남쪽, ^는 북쪽이다.
세 번째 줄에 당신이 로봇에 내려야 하는 명령어들을 공백 없이 명령을 내릴 순서대로 출력한다. 이 문자열의 길이가 곧 당신이 내리는 명령어의 개수이며, 명령어의 개수를 최소화해야 정답 처리된다.
명령어의 개수를 최소화하면서 목표를 달성할 수 있는 방법이 여러 가지라면, 그 중 한 가지를 아무거나 출력하면 된다.
추가설명
이 문제의 경우 목표를 달성할 수 있는 방안이 여러개 일 수 있으며 그 중 아무 것이나 출력해도 답으로 처리된다.
아래의 입출력 예제를 보면, 하나의 입력에 대해 각각 달성할 수 있는 방안(출력)이 2개씩 존재한다. [1-1, 1-2], [2-1,2-2]
두 가지 방안 중 하나가 정답으로 출력된 경우 정답으로 인정된다.
예시1
입력
5 8
#######.
........
........
........
........
Plain Text
복사
출력1
1 1
>
AAA
Plain Text
복사
출력2
1 7
<
AAA
Plain Text
복사
예시2
입력
9 14
.......###....
.........#....
.#####...###..
.#.........#..
.#.#####...###
.#.#...#.....#
.###.###.....#
.....#.......#
.....#########
Plain Text
복사
출력1
3 6
<
AALAALALARAARARALALAAAALAALARALARALA
Plain Text
복사
출력2
1 8
>
ARALARALARAARAAAARARALALAALARARAARAA
Plain Text
복사
정답
import sys
H, W = list(map(int, sys.stdin.readline().split()))
dy=[-1,1,0,0]
dx=[0,0,-1,1]
# 보드 만들기
board = []
for i in range(H):
board.append(list(sys.stdin.readline().rstrip()))
# 시작점 찾기 -> 붙어있는 '#'이 하나만 있는 경우
# 완전 탐색으로 진행
is_break = False
for i in range(H):
for j in range(W):
if board[i][j] == '#':
y, x = i, j
cnt = 0
direction = []
for s in range(4):
new_y = y + dy[s]
new_x = x + dx[s]
if (new_y<0) or (new_y>=H) or (new_x<0) or (new_x>=W): continue
if board[new_y][new_x] == '#':
cnt += 1
direction.append(s)
if cnt == 1:
is_break = True
start = [y,x]
break
if is_break == True:
break
first_direction = direction[0] # 시작 방향: 시작점과 붙어있는 '#'의 위치
direction = first_direction # 로봇의 방향
command = [] # 명령어 모음
visited = [[False]*W for _ in range(H)] # 이미 방문한 곳은 중복 방문하지 않도록 설정
visited[start[0]][start[1]] = True
current = start
# BFS 방식으로 인접해있는 '#'으로 방향을 돌리거나 이동.
while True:
cnt = 0 # 인접해있는 '#'의 개수
for i in range(4):
new_y = current[0] + dy[i]
new_x = current[1] + dx[i]
if (new_y<0) or (new_y>=H) or (new_x<0) or (new_x>=W): continue
if (board[new_y][new_x] == '#') and (visited[new_y][new_x]==False):
cnt += 1
heading = i # 인접해있는 '#'의 위치
break
if cnt == 0: # 끝점에 도착하는 경우
break
else:
if direction == 0: # 로봇이 위를 향하고 있을 때
if heading == 0: # 위로 '#'이 이어진 경우
command.append('A') # 2칸 이동
visited[current[0]-1][current[1]] = True
visited[current[0]-2][current[1]] = True
current = [current[0]-2, current[1]]
elif heading == 2: # 왼쪽에 '#'이 있는 경우
command.append('L') # 왼쪽으로 돌기
direction = 2
elif heading == 3: # 오른쪽에 '#'이 있는 경우
command.append('R') # 오른쪽으로 돌기
direction = 3
if direction == 1: # 로봇이 아래를 향하고 있을 때
if heading == 1: # 아래쪽에 '#'이 이어지는 경우
command.append('A') # 아래로 두 칸 이동
visited[current[0]+1][current[1]] = True
visited[current[0]+2][current[1]] = True
current = [current[0]+2, current[1]]
elif heading == 2: # 왼쪽에 '#'이 있는 경우
command.append('R') # 오른쪽으로 돌기
direction = 2
elif heading == 3: # 오른쪽에 '#'이 있는 경우
command.append('L') # 왼쪽으로 돌기
direction = 3
if direction == 2: # 로봇이 왼쪽을 향하고 있을 때
if heading == 2: # 왼쪽에 '#'이 있는 경우
command.append('A') # 왼쪽으로 두 칸 이동
visited[current[0]][current[1]-1] = True
visited[current[0]][current[1]-2] = True
current = [current[0], current[1]-2]
elif heading == 0: # 위쪽에 '#'이 있는 경우
command.append('R') # 오른쪽으로 돌기
direction = 0
elif heading == 1: # 아래쪽에 '#'이 있는 경우
command.append('L') # 왼쪽으로 돌기
direction = 1
if direction == 3: # 로봇이 오른쪽을 향하고 있을 때
if heading == 3: # 오른쪽에 '#'이 있는 경우
command.append('A') # 오른쪽으로 두 칸 이동
visited[current[0]][current[1]+1] = True
visited[current[0]][current[1]+2] = True
current = [current[0], current[1]+2]
elif heading == 0: # 위쪽에 '#'이 있는 경우
command.append('L') # 왼쪽으로 돌기
direction = 0
elif heading == 1: # 오른쪽에 '#'이 있는 경우
command.append('R') # 오른쪽으로 돌기
direction = 1
# 형식에 맞도록 출력
if first_direction == 0:
first_direction = '^'
elif first_direction == 1:
first_direction = 'v'
elif first_direction == 2:
first_direction = '<'
else:
first_direction = '>'
print(f'{start[0]+1} {start[1]+1}')
print(first_direction)
print(''.join(command))
Python
복사
풀이
•
완전 탐색과 BFS 방식을 사용하여 풀었다.
•
우선 시작점(또는 끝점)은 사방탐색을 진행했을 때 인접해있는 ‘#’의 개수가 한 개인 곳이다. (중간에 위치한 곳이면 무조건 2개이다.)
•
따라서 완전탐색을 진행하여 그러한 조건을 만족하는 시작점(또는 끝점)을 찾았다.
# 시작점 찾기 -> 붙어있는 '#'이 하나만 있는 경우
# 완전 탐색으로 진행
is_break = False
for i in range(H):
for j in range(W):
if board[i][j] == '#':
y, x = i, j
cnt = 0
direction = []
for s in range(4):
new_y = y + dy[s]
new_x = x + dx[s]
if (new_y<0) or (new_y>=H) or (new_x<0) or (new_x>=W): continue
if board[new_y][new_x] == '#':
cnt += 1
direction.append(s)
if cnt == 1:
is_break = True
start = [y,x]
break
if is_break == True:
break
Python
복사
•
이때 로봇을 처음에 두는 방향은 시작점과 인접해있는 ‘#’의 방향이다.
•
예를 들어 [0,7]이 시작점이고 ‘#’이 [0,8]로 이어져있다면, 로봇을 오른쪽으로 두어야 한다.
•
우리는 인접해있는 ‘#’의 방향을 direction에 이미 저장했기 때문에 direction을 불러오면 된다.
first_direction = direction[0] # 시작 방향: 시작점과 붙어있는 '#'의 위치
Python
복사
•
그리고 로봇이 어느 방향으로 도는지를 알아야 하기 때문에 현재 로봇이 향하고 있는 방향을 저장하는 변수를 만들어준다.
direction = first_direction # 로봇의 방향
Python
복사
•
다음으로는 BFS 방식을 사용하여 인접해있는 ‘#’의 위치를 찾고 만약 인접해있는 ‘#’의 위치가 현재 로봇의 방향과 일치한다면 명령어 ‘A’를 입력하고 그 곳으로 두 칸 이동한다. 만약 다르다면 그쪽 방향을 향해 도는 명령어를 입력한다. 이를 인접한 ‘#’이 나타나지 않을 때까지 반복한다.
while True:
cnt = 0 # 인접해있는 '#'의 개수
for i in range(4):
new_y = current[0] + dy[i]
new_x = current[1] + dx[i]
if (new_y<0) or (new_y>=H) or (new_x<0) or (new_x>=W): continue
if (board[new_y][new_x] == '#') and (visited[new_y][new_x]==False):
cnt += 1
heading = i # 인접해있는 '#'의 위치
break
if cnt == 0: # 끝점에 도착하는 경우
break
else:
if direction == 0: # 로봇이 위를 향하고 있을 때
if heading == 0: # 위로 '#'이 이어진 경우
command.append('A') # 2칸 이동
visited[current[0]-1][current[1]] = True
visited[current[0]-2][current[1]] = True
current = [current[0]-2, current[1]]
elif heading == 2: # 왼쪽에 '#'이 있는 경우
command.append('L') # 왼쪽으로 돌기
direction = 2
elif heading == 3: # 오른쪽에 '#'이 있는 경우
command.append('R') # 오른쪽으로 돌기
direction = 3
if direction == 1: # 로봇이 아래를 향하고 있을 때
if heading == 1: # 아래쪽에 '#'이 이어지는 경우
command.append('A') # 아래로 두 칸 이동
visited[current[0]+1][current[1]] = True
visited[current[0]+2][current[1]] = True
current = [current[0]+2, current[1]]
elif heading == 2: # 왼쪽에 '#'이 있는 경우
command.append('R') # 오른쪽으로 돌기
direction = 2
elif heading == 3: # 오른쪽에 '#'이 있는 경우
command.append('L') # 왼쪽으로 돌기
direction = 3
if direction == 2: # 로봇이 왼쪽을 향하고 있을 때
if heading == 2: # 왼쪽에 '#'이 있는 경우
command.append('A') # 왼쪽으로 두 칸 이동
visited[current[0]][current[1]-1] = True
visited[current[0]][current[1]-2] = True
current = [current[0], current[1]-2]
elif heading == 0: # 위쪽에 '#'이 있는 경우
command.append('R') # 오른쪽으로 돌기
direction = 0
elif heading == 1: # 아래쪽에 '#'이 있는 경우
command.append('L') # 왼쪽으로 돌기
direction = 1
if direction == 3: # 로봇이 오른쪽을 향하고 있을 때
if heading == 3: # 오른쪽에 '#'이 있는 경우
command.append('A') # 오른쪽으로 두 칸 이동
visited[current[0]][current[1]+1] = True
visited[current[0]][current[1]+2] = True
current = [current[0], current[1]+2]
elif heading == 0: # 위쪽에 '#'이 있는 경우
command.append('L') # 왼쪽으로 돌기
direction = 0
elif heading == 1: # 오른쪽에 '#'이 있는 경우
command.append('R') # 오른쪽으로 돌기
direction = 1
Python
복사
•
그 다음에는 형식에 맞게 답을 출력한다.
# 형식에 맞도록 출력
if first_direction == 0:
first_direction = '^'
elif first_direction == 1:
first_direction = 'v'
elif first_direction == 2:
first_direction = '<'
else:
first_direction = '>'
print(f'{start[0]+1} {start[1]+1}')
print(first_direction)
print(''.join(command))
Python
복사