시뮬레이션 (Simulation) 알고리즘

00 개요

• 목표: 코딩테스트 뽀개기!

01 시뮬레이션

1. 시뮬레이션이란

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

2. 준비하기

• 다른 알고리즘들과 달리, 상황을 보고 판단!

3. 연습 문제: 백준 14503 로봇 청소기

• 링크: https://www.acmicpc.net/problem/14503
  • 비고: 현재는 웹사이트에 없는 문제

1) 문제

• Q:
  • 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
  • 로봇 청소기가 있는 장소는 N x M 크기의 직사각형으로 나타낼 수 있으며, 1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 
  • 로봇 청소기는 다음과 같이 작동한다.
    1. 1. 현재 위치를 청소한다.
    2. 2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
       1. a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
       2. b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
       3. c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
       4. d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
  • 로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
• 입력:
  • 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 <= N, M <= 50)
  • 둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.
  • 셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.
  • 로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.
• 출력:
  • 로봇 청소기가 청소하는 칸의 개수를 출력한다.
• 예제 입력 1:

3 3

1 1 0

1 1 1

1 0 1

1 1 1

• 예제 출력 1:

1

2) 사전 계획 수립

• 아이디어
  • while문으로 특정 조건 만족하는 한 계속 이동
  • for문으로 4방향 탐색 먼저 수행
    • 빈 칸 있을 경우 → 이동
    • 4방향 탐색 안 될 경우 → 뒤로 한 칸 가서 반복
  • while문 안에서 특정 조건인 경우에 종료: break
    • i.e., 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우
• 시간 복잡도
  •  
  • while문 최대: N * M
  • 각 칸에서 4방향 연산 수행
  • O(NM)
    • 설명:
      • 원래는 O(세로 * 가로 * 4방향) = N * M * 4 인데
      • 시간 복잡도에서 상수 (i.e., 4)가 곱해진 것은 제거 가능하므로 O(NM) 
  • O(NM) = N * M
    • N, M 최대값 = 50, 50
    • 50^2 = 2500 < 2억이므로 가능 (주의: 다른 분은 500만번을 Max로 권장)
• 자료 구조
  • 전체 지도: int[ ][ ]
    • 0: 청소 안 한 곳
    • 1: 벽
    • 2: 청소 한 곳
    • 설명: 청소 여부를 나타내는 변수 (예, checked=[][])를 따로 만드는 것보다, 복잡도를 줄이기 위해 이미 제공된 전체 지도에 변수 2를 '청소 한 곳'을 나타내는 것으로 지정하여 사용
  • 로봇 청소기 위치, 방향: int, int, int
    • y, x, d
  • 전체 청소된 칸의 개수: int
    
    • count

3) 실습

# 예제 1
N, M = 3, 3
y, x, d = 1, 1, 0
data = '''
1 1 1
1 0 1
1 1 1
'''
# 예제 1 출력값: 1

# 예제 2
N, M = 11, 10
y, x, d = 7, 4, 0
data = '''
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
'''
# 예제 2 출력값: 57

# input을 요구하는 경우
# import sys
# input = sys.stdin.readline
# N, M = map(int, input().split())
# y, x, d = map(int, input().split())
# mapped_list = [list(map(int, input().split())) for _ in range(N)]

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

while True:
    if mapped_list[y][x] == 0:
        mapped_list[y][x] = 2
        count += 1
    flag = 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 mapped_list[ny][nx] == 0:
                # 그 방향으로 회전(d 재정의)한 다음 한 칸을 전진(y, x 재정의)하고 1번부터 진행(while문 처음으로 가기)
                d = (d-i+4) %4
                y = ny
                x = nx
                flag = True # 청소 여부 플래그
                break
    # 4방향 모두 벽/청소한 경우, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번부터 진행
    if flag == False:
        # 바라보는 방향을 유지한 채로 한 칸 후진하고 2번부터 실행
        # 뒤쪽 방향이 막혀있는지 확인
        ny = y - dy[d]
        nx = x - dx[d]
        if 0 <= ny <= N and 0 <= nx <= M:
            if mapped_list[ny][nx] == 1: # 뒤가 1(벽)인 경우
                break # while문 탈출
            else:
                y = ny
                x = nx
        else:
            break
print(count)

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

 

참조

1. 개발자 장고, https://www.youtube.com/watch?v=ql82YcFisUI&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=5 
2.