[BOJ] 2174. 로봇 시뮬레이션(Python) / Simulation

2174번: 로봇 시뮬레이션

문제명 그대로 주어진 대로 로봇을 움직이는 Simulation 문제이다.

# 1시간 59분 소요. 한 번에 pass. 시간, 메모리 1위를 달성

• 사용 알고리즘 : 구현
• 맵은 사용하지 않고, 로봇 정보와 위치 정보를 모두 파이썬 Dictionary를 사용했다.
• 문제 풀기 전에 미리 해둔 것
  • 상하좌우 delta 좌표로 구현(dr, dc)
  • 상하좌우 => NSWE => 0, 1, 2, 3으로 딕셔너리에 방향 정보 저장(dirInfo)
  • "L" 또는 "R" 명령어를 수행할 때 방향 전환하기 위한 상하좌우 위치별 방향 전환 정보 저장 (changeDir)
• 로봇 초기 위치 Input 받을 때 다루기 편하게 x, y를 일반적인 이차원 배열의 좌표로 변환(sr, sc)
• robotInfo - 로봇 번호 : (현재 로봇 위치, 방향) 정보 저장
• posInfo -  위치 : 로봇 번호 정보 저장
• moveRobot() 함수에서 로봇 이동 (번호, 명령어, 반복 횟수) 정보 인자로 받으면 명령어 수행
  • 현재 로봇의 위치(r, c)와 방향(d)에서
  • 회전 명령이면, L 또는 R 방향으로 90도로 cnt번 회전 
    
    • 이 때, 4번 90도로 회전하면 원 위치 되므로 4로 나눈 나머지만큼 주어진 방향으로 changeDir을 참조하여 회전
    • 전환한 방향 정보 robotInfo에 저장
  • 직진 명령이면, d방향으로 cnt칸 만큼 이동
    • 이 때, 원래의 로봇 정보와 위치 정보는 삭제하고 이동 후의 로봇 정보와 위치 정보를 새로 등록
    • 이동 중에 벽을 만나면 출력 형식대로 출력 후 시스템 종료
    • 이동 중에 다른 로봇 만나면 posInfo에서 해당 위치로 충돌한 로봇의 번호와 함께 출력 형식대로 출력 후 시스템 종료
    • 이동 후, 로봇 정보와 위치 정보를 새로 등록
• 정상적으로 문제 없이 모든 명령을 수행했다면 "OK" 출력
• 자세한 내용은 아래 코드에 주석으로 달아놓았다!

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

# 상, 하, 좌, 우 = 0, 1, 2, 3
dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)
dirInfo = {"N": 0, "S": 1, "W": 2, "E": 3}
changeDir = {"L" : (2, 3, 1, 0), "R": (3, 2, 0, 1)}

# 로봇 이동 함수 - (번호, 명령어, 반복 횟수) 정보 인자로 받음
def moveRobot(num, cmd, cnt):
    global robotInfo, posInfo
    r, c, d = robotInfo[num]    # 현재 로봇 위치, 방향
    
    # 회전 명령 - L 또는 R 방향으로 90도로 cnt번 회전  
    if cmd in "LR":
        cnt %= 4        # 4번 돌면 제자리이므로 4로 나눈 나머지를 취함
        for _ in range(cnt):
            d = changeDir[cmd][d]
        nd = d
        robotInfo[num][2] = nd       # 새로운 방향 등록 

    # 직진 명령 - d방향으로 cnt칸 만큼 이동
    else:
        del robotInfo[num]          # 해당 로봇 정보 삭제
        del posInfo[(r, c)]         # 해당 위치 정보 삭제
        for _ in range(cnt):
            nr = r + dr[d]
            nc = c + dc[d]

            if not (0 <= nr < R and 0 <= nc < C):           # 격자 밖으로 나가면
                print("Robot", num, "crashes into the wall")
                exit()
            
            elif (nr, nc) in posInfo.keys():                # 놓여있는 로봇과 충돌하면
                print("Robot", num, "crashes into robot", posInfo[(nr, nc)])
                exit()
            r, c = nr, nc

        robotInfo[num] = [r, c, d]       # 이동한 로봇 정보 새로 등록
        posInfo[(r, c)] = num            # 이동한 위치 정보 새로 등록

# main
C, R = map(int, input().split())
N, M = map(int, input().split())

robotInfo = dict()      # 로봇별 정보 저장
posInfo = dict()        # 위치별 정보 저장
for n in range(1, N+1):
    x, y, d = list(input().split())
    sr = R-int(y)
    sc = int(x)-1
    robotInfo[n] = [sr, sc, dirInfo[d]]     # 로봇 번호 : (현재 로봇 위치, 방향) 정보 저장
    posInfo[(sr, sc)] = n                   # 해당 위치에 현재 있는 로봇 번호 저장

for _ in range(M):
    num, cmd, cnt = list(input().split())
    moveRobot(int(num), cmd, int(cnt))        # (로봇 번호, 명령어(L, R, F), 반복 횟수)

print("OK")

---

• 시간 : 104ms / 메모리 : 121220kb
• 고찰 : 문제 풀기 전에 어떻게 풀지 꼼꼼하게 구상했다. 그럼에도 2시간 가까운 시간이 걸렸다ㅠㅠ 그래도 한번에 통과했고, 시간, 메모리 1위를 달성해 기분 좋았다. 시뮬레이션 문제 중에 맵을 만들지 않고도 풀 수 있는 문제들이 종종 나온다. 맵을 그리는 것보다 사실 코드가 더 깔끔하고 메모리, 시간 효율적인 면에서 딕셔너리 사용이 월등하다고 생각한다.(O(1)로 키값에 대응하는 value값을 가져올 수 있기 때문!) 또 문제 풀러 가야겠다~~~~~