시뮬레이션과 완전 탐색을 활용해야 하는 구현 문제 !
📈금융 개발 블로그 : https://quantpro.co.kr/
📌 문제 설명
배경 : 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
-
현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
-
캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
-
만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우네는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
-
첫줄에는 맵의 크기, 둘쨰줄에는 좌표와 서있는 방향, 마지막에는 맵을 input
🥕입력예시
4 4 # 4 x 4 맵 생성
1 1 0 # (1, 1)에 북쪽(0)을 보고 서 있는 캐릭터
1 1 1 1 # 바다 바다 바다 바다
1 0 0 1 # 바다 육지 육지 바다
1 1 0 1 # 바다 바다 육지 바다
1 1 1 1 # 바다 바다 바다 바다
🥕출력예시
3
📌 문제 풀이
-
좌표이동 문제는 x,y 좌표 연산을 통해 이동해야 한다. 따라서 동 서 남 북으로 이동하면 좌표가 어떻게 증감 해야하는지 항상 임지하고 있어야 한다!
-
주어진 맵과 똑같은 맵을 하나 더 만들어서 직접 만든 맵에 0,1과 같이 도착한 곳을 체크하자! 왜냐면 3번 조건에사와 같이 1이 바다인 경우를 구별해야한다!
-
좌표가 없는 맵 밖의 좌표 예외처리도 항상 생각하자!
n, m = map(int, input().split())
#방문할 위치를 저장할 맵 제작
d = [[0]* m for _ in range(n)]
#캐릭터의 x,y 방향 입력받기
x,y, direction = map(int, input().split())
d[x][y]=1
arr = []
for i in range(n):
arr.append(list(map(int, input().split())))
# 북 동 남 서 방향 정의
dx = [-1 , 0, 1,0]
dy = [0,1,0,-1]
#direction을 global로 선언하여 방향값 저장
def turn_left():
global direction
direction -= 1
if direction == -1:
direction =3
cnt = 1
turn_time = 0
while True:
turn_left()
nx = x + dx[direction]
ny = y + dy[direction]
# 접근 가능하다
if d[nx][ny] ==0 and arr[nx][ny] ==0:
d[nx][ny]=1
x = nx
y = nx
cnt += 1
turn_time = 0
continue
else:
turn_time +=1
# 4번 돌아도 갈곳이 없다
if turn_time ==4 :
nx = x -dx [direction]
ny = y- dy[direction]
if arr[nx][ny] == 0 :
x =nx
y= nx
else :
break
turn_time = 0
print(cnt)
