이 문제는 왕실의 나이트 처럼 좌표평면에서 시뮬레이션하는 알고리즘이다.
다만, 이 문제는 주어진 조건도 훨씬 길고 복잡해서 확실히 어렵다.
이 문제 풀이의 특징은 내가 방문한 곳을 체크하기 위한 2차원 배열과 육지와 땅이 표현된 2차원 배열을 이원화한다는 점이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 맵 크기 결정
n, m = map(int, input().split())
# 현재 위치와 바라보는 방향 입력
x, y, d = map(int, input().split())
# 방문한 위치를 표시하기 위한 2차원 배열
c_map = [[0]*m for _ in range(n)]
"""
n = m = 4일때, c_map은
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
"""
# 현재 위치를 방문 처리
c_map[x][y] = 1
"""
현재위치(x = y= 1)를 방문처리 하면, c_map은
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
"""
# 2차원 배열로 맵 입력받아 그리기
arr = []
for i in range(n):
arr.append(list(map(int, input().split())))
"""
예제의 인풋 값을 그대로 받는 경우 arr은
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1
"""
좌표평면 상에서 이동을 시뮬레이션 할때는 각 조건에 따라 x,y 값이 어떻게 변화하는지를 지정하는것이 좋다.
이코테에서는 보통 dx, dy로 각 조건에 따른 x,y 변화량을 배열로써 지정해주도록 하고있다.
특히 이 문제에서는 북, 동, 남, 서를 0, 3, 2, 1로 표시하는데, 꽤나 친절하게 dx,dy에서 인덱싱으로 각 값을 매칭하도록 유도해주고 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# 바라보는 방향이 북, 동, 남, 서 일때, x,y값 변화를 배열로 표시
# 북 서 남 동 = 0 3 2 1
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 왼쪽으로 회전하는 함수
# 시계방향으로 회전할 때, 각 방향에 값이 1씩 감소
# 단, 북에서 서로 회전할때는 -1이 되므로 별도의 조건을 걸어 d = 3이 되도록 함
def turn_left():
global d
d -= 1
if d == -1:
d = 3
# 시뮬레이션
# count는 방문한 칸의 수인데, 시작위치는 방문한 것으로 설정하기 때문에 최초값을 1로 설정함
count = 1
# 각 좌표에서 왼쪽으로 회전한 횟수
turn_time = 0
while True:
# 왼쪽으로 회전
turn_left()
# 이동
nx = x + dx[d]
ny = y + dy[d]
# 만약 회전한 후, 정면에 가보지 않았고 육지인 칸이 존재하면 이동
if d[nx][ny] == 0 and arr[nx][ny] == 0:
d[nx][ny] = 1
x = nx
y = ny
count += 1
turn_time = 0
continue
# 회전한 후, 정면에 가보지 않은 칸이 없거나 바다인 경우, 왼쪽으로의 회전만 수행
else:
turn_time += 1
# 네 방향 모두 갈 수 없는 경우, 바라보는 방향을 유지한채 한칸 뒤로 이동
if turn_time == 4:
nx = x - dx[d]
ny = y - dy[d]
# 만약, 뒤로 이동할 수 있다면 이동
if arr[nx][ny] == 0:
x = nx
y = ny
# 뒤가 바다인 칸이라 이동할수 없다면, loop 종료
else:
break
turn_time = 0
print(count)
나는 답을 거의 보면서 풀었다. 이런 난이도의 문제를 처음 접해봐서 그렇다는 핑계로 답을 보면서 이를 해석하는 방식으로 공부했다.
지금 시점에서야 코드에 대한 이해가 되니 메커니즘을 순서대로 잘 정리한다면 생각보다 쉽게 풀수도 있지않나 하는 생각이 드는데, 사실 실전에서 이게 가능할 정도로 실력이 는다는건 너무 먼 이야기처럼 느껴지긴한다.
반복적으로 연습해서 언제든 이런 복잡한 메커니즘의 알고리즘을 마주했을 때, 진행 순서를 뚜렷하게 정돈할 수 있을 정도가 되어야 이 정도 난이도의 문제를 실전에서 해결할 수 있을듯하다.