정답 코드
h, w = map(int, input().split())
maps = []
direct = {0:'>', 1:'<',2:'v', 3:'^'}
ans = [[0, 0, 0, 'a'*1000], '']
total = 0
for i in range(h):
temp = input()
total += temp.count('#')
maps.append(temp)
def turn(cur, nex):
if cur == 0:
if nex == 2:
ans[1] += 'R'
else:
ans[1] += 'L'
elif cur == 1:
if nex == 2:
ans[1] += 'L'
else:
ans[1] += 'R'
elif cur == 2:
if nex == 0:
ans[1] += 'L'
elif nex == 1:
ans[1] += 'R'
else:
if nex == 0:
ans[1] += 'R'
elif nex == 1:
ans[1] += 'L'
def dfs(r, c, v, initial, direction, cnt):
global ans
if total == cnt:
if ans[1] < ans[0][3]:
ans[0][0], ans[0][1] = initial[0] + 1, initial[1] + 1
ans[0][2] = direct[initial[2]]
ans[0][3] = ans[1]
return
if direction == 0:
v[r][c], v[r][c - 1] = True, True
elif direction == 1:
v[r][c], v[r][c + 1] = True, True
elif direction == 2:
v[r][c], v[r - 1][c] = True, True
else:
v[r][c], v[r + 1][c] = True, True
pr = [0, 0, 1, -1]
pc = [1, -1, 0, 0]
for i in range(4):
nr = r + pr[i]
nc = c + pc[i]
nr2 = r + pr[i] + pr[i]
nc2 = c + pc[i] + pc[i]
if 0 <= nr2 < h and 0 <= nc2 < w and not v[nr2][nc2] and maps[nr][nc] == '#' and maps[nr2][nc2] == '#':
if direction != i:
turn(direction, i)
ans[1] += 'A'
dfs(nr2, nc2, v, initial, i, cnt + 2)
def check(r, c):
v = [[False for i in range(w)] for j in range(h)]
v[r][c] = True
pr = [0, 0, 1, -1]
pc = [1, -1, 0, 0]
for i in range(4):
nr = r + pr[i]
nc = c + pc[i]
nr2 = r + pr[i] + pr[i]
nc2 = c + pc[i] + pc[i]
if 0 <= nr2 < h and 0 <= nc2 < w and maps[nr][nc] == '#' and maps[nr2][nc2] == '#':
ans[1] += 'A'
dfs(nr2, nc2, v, [r, c, i], i, 3)
sp = []
for i in range(h):
for j in range(w):
if maps[i][j] == '#':
cnt = 0
pr = [0, 0, 1, -1]
pc = [1, -1, 0, 0]
for k in range(4):
nr = i + pr[k]
nc = j + pc[k]
if 0 <= nr < h and 0 <= nc < w and maps[nr][nc] == '#':
cnt += 1
if cnt == 1:
sp.append([i, j])
for s in sp:
ans[1] = ''
check(s[0], s[1])
print(ans[0][0], ans[0][1])
print(ans[0][2])
print(ans[0][3])풀이 방법
A 명령이 로봇을 두 칸씩 앞으로 보내고, 한 번 방문한 칸은 다시 방문하지 않는다는 조건으로 인해, 입력으로 주어지는 사수의 경로는 반드시 아래와 같이 경로 외적인 이유로 붙어 있는 경우가 없다.
(불가능한 경우)
[1-9A-Z 순으로 방문순서 표시]
..1234567....
....CBA98.... <-- 7 지점에서 A 명령으로 8과 9를 거칠 방법이 없음
....DEFGHI...(가능한 경우)
..1234567....
........8....
...EDCBA9.... <-- 이렇게 두 칸이 인접한 경우는 경로 상에서 인접한 경우밖에 없음
...F.........
...GHIJ......따라서 입력만 봐도 로봇이 지나가야 하는 경로가 어떻게 생겼는지를 바로 알 수 있다.
맨 끝 지점에서 다른 쪽 끝 지점까지 #만을 타고 계속 따라가면 된다.
처음 로봇을 어디에 어떤 방향으로 놓을지 찾기
맨 끝 지점은,
· 자기 칸이 #이면서,
· 인접한 칸들 중 #가 정확히 한 개 있는지점
이러한 지점은 총 2개가 있으며, 조건문을 통해 로봇을 어떤 칸에 놓아야 하는지를 알 수 있다.
로봇의 방향의 경우, 로봇이 인접한 # 쪽을 향하게 놓아야 불필요한 회전을 하지 않는다.
경로 따라가기
#칸이 맨 끝 지점이 아니라면, 인접한 칸들 중 #는 정확히 두 개 일 것입니다.
두 개 중 한 칸은 이미 지나온 칸이고, 나머지 한 칸이 아직 방문하지 않은 칸이다.
아직 방문하지 않은 칸으로 이동을 하면 된다.
다만 로봇은 방향을 가지기 때문에 회전에 대한 처리를 고민해야 한다.
변수로 "현재 주인공이 바라보고 있는 방향" (direction)을 저장해 두고, 각 방향마다 "그 방향으로 이동하면 좌표가 어떻게 바뀌는지 계산해 둔다(북→동→남→서).
이는 북쪽에는 0, 동쪽에는 1, 남쪽에는 2, 서쪽에는 3의 index를 대응시킨 것으로, 이러한 순서대로 방향을 숫자에 대응한 이유는 index를 1 증가하면 오른쪽으로 90도 회전, 1 감소시키면 왼쪽으로 90도 회전한 것으로 볼 수 있어서 처리가 용이하기 때문이다.
매번 현재의 방향 (now_direction)과 다음 칸으로 이동하기 위해 봐야 하는 방향 (target_direction)을 비교하여 왼쪽 또는 오른쪽으로 회전하면 된다.
명령어의 횟수를 최소화해야 하므로, 만약 왼쪽 90도 회전 한 번이면 될 것을 오른쪽 90도 회전 세 번을 하는 식으로 처리하면 오답 처리된다.
알고리즘 유형
DFS
