[Coding Test] 3.코딩테스트 Simulation

[공지사항] [‘코딩테스트 필수 알고리즘’ 강의를 듣고 이해한 내용을 바탕으로 직접 필기한 내용입니다. ] 👉🏻바로가기

시뮬레이션(구현)

• 각 조건에 맞는 상황을 구현하는 문제
  • 지도상에서 이동하면서 탐험? 하는 문제
  • 배열 안에서 이동하면서 탐험? 하는 문제
• 별도의 알고리즘 없이 풀수 있으나, 구현력이 중요
• 매 시험마다 1문제 이상 무조건 출제;

시뮬레이션 기본 문제 : 백준 14503

아이디어

• 특정 조건을 만족하는 한 계속 이동 -> While 문, 조건만족 x break
• 4방향 탐색 먼저 수행 > 빈칸 있을 경우 이동
• 4방향 탐색 안될 경우, 뒤로 한칸 가서 반복

시간복잡도

• While문의 최대는 : N * M(로봇청소기 위치) * 4(방향)
• N * M

자료구조

• 전체 지도 : int[][]
• 내 위치, 방향 : int, int, int
  • 시간 복잡도를 위해 0 : 청소 x, 1 : 벽, 2 : 청소 로 구성하면 2차원 배열이 필요 없어짐.
• 전체 청소 구간 cnt : int

"""
1. 아이디어
- while 문으로, 특정 조건 종료할때까지 반복
- 4방향을 for문으로 탐색
- 탐색 불가능할 경우, 뒤로 한칸 후진
- 후진 불가능하면 종료.

2. 시간복잡도
- O(MN) : 50^2 = 2500<2억

3. 자료구조
- map : int[][]
- 로봇청소기 위치, 방향, 전체 청소한 곳 수 

"""


import sys
input = sys.stdin.readline

N,M = map(int, input().split()) 
y,x,d = map(int, input().split())

map = [list(map(int, input().split)) for _ in range(N)]
cnt = 0
dy = [-1,0,1,0]
dx = [0,1,0,-1]

while 1:
  if map[y][x] == 0:
  map[y][x] = 2
  cnt += 1
  sw = False
  for i in range(1,5):
    ny = y + dy[d-i]
    nx = x + dx[d-i]
    if 0 <=ny <N and 0<=nx<M:
    	if map[ny][nx] == 0:
      # 그뱡향으로 회전한 다음 한칸을 전진하고 1번부터 진행
       d = (d-i+4) % 4
       y = ny
     	 x = nx
     	 sw = True
     	 break
  
  #4방향 모두 있지 않은 경우.
  if sw == False:
    #바라보는 방향 유지한채로 한칸 후진후 2번으로 돌아감
    #뒤쪽 벽이 막혀있는지 확인
    ny = y - dy[d]
    nx = x - dx[d]
  	if 0 <=ny <N and 0 <= nx < M:
      if map[ny][nx] == 1:
        break
      else:
        y = ny
        x = nx
    else:
      break
      
print(cnt)
        
    	
  
"""
문제에 방향 벡터가 북쪽 0, 동쪽 1, 남쪽 2, 서쪽 3 으로 주어짐
시계방향 회전, 올라가는것은 -, 내려가는것은 +
			(-1,0)
(0,-1)			(0,1)
			(1,0)
			
형태이다.

dx = [0,1,0,-1]
dy = [-1,0,1,0]

문제에서는 왼쪽 방향부터 탐색한다 했으므로 index를 한칸씩 뒤로 가는 것과 동일
"""

Tip

• 주어진 조건을 되도록 그대로 구현(나중에 매우 헷갈림)
• 되도록 쉽게 구현
  • 최악 케이스 : 코드 복잡해 디버깅이 안됨, 시간 대부분 소모
• Console에 Log 찍는 것 연습