4. 시뮬레이션

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

 

 

백준 1403 로봇청소기문제

https://www.acmicpc.net/problem/14503

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

 

 

- 아이디어

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

- 시간복잡도

• while문 최대 : N X M (로봇청소기가 돌아다닐 수 있는 총 면적) O
• 각 칸에서 4방향 연산 수행
• O ( N X M X 4) => 연산 시 상수 곱셉은 없앨 수 있음 = > O (N X M) => 2억 초과 여부만 확인.

- 자료구조

• 전체 지도 : int [] []
• 내 위치, 방향 : int(y), int(x), int(d)
• 청소x : 0 , 벽 : 1, 청소o : 2  <= 2차원 표시하지말고 복잡도를 줄임.
• 전체, cnt(int)

"""
0.문제
  1.현재 위치를 청소한다.
  2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.

1. 아이디어
- while문으로, 특정조건 종료될때까지 반복
- 4방향을 for문으로 탐색
- 더이상 탐색 불가능할 경우, 뒤로 한칸 후진
- 청소x : 0 , 벽 : 1, 청소o : 2 

2. 시간복잡도
- O(NM) : 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]

# a.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 
#   그 방향으로 회전한 다음 한칸을 전진하고 1번부터 진행.
while 1:
	# 청소가 안되어있는 경우에만 청소하기 조건
	if map[y][x] == 0:
        map[y][x] = 2
        cnt += 1
    sw = False
    # 2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.   
    for i in range(1,5):
  		ny = y + dy[d-i]
		nx = x + dx[d-i]
        # 현재 지도안에 들어오는지 조건확인.
    	if 0<=ny<N and 0<=nx<M:
		    # b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
		if map[ny][nx] == 0: 
                # 그 방향으로 회전한 다음 한칸을 전진하고 1번부터 진행.
                # 현재 위치가 탐색한 경우.
                # d 가 -가 되면 안됨.
                d = (d-i+4) %4
                y = ny
                x = nx
                sw = True
                break
    # c. 4 방향 모두 청소가 이미 되어있거나 벽인 경우에는, => switch로 구분.
    #   바라보는 뱡향을 유지한채로 한칸 후진하고 2번으로 돌아간다. 
    if sw == False:        	
    	# 바라보고 있는 방향에서 뒤쪽 방향이 막혀있는지 확인
        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)

* 파이썬 특징

dy[-1] 일 경우 0인덱스값이 뒤로 와서 -1값으로 출력됨. 가지고 있는 인덱스 값까지의

-값만 뒤로 돌아서 값을 return해주고 초과되는 인덱스값은 오류가 남.

 

 

* Tip

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

 

https://www.youtube.com/watch?v=ql82YcFisUI&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=5