성실하게 시뮬레이션 구현하기.. -로봇 청소기-

1. 문제

 

14503번: 로봇 청소기 (acmicpc.net)

14503번: 로봇 청소기

 

주어진 조건에 따라 움직이는 로봇 청소기가 청소하는 영역의 수를 구하는 문제

 

 

2. 풀이

 

어렵게 생각하지 말고 항상 성실하게 구현하면 풀린다는 마음가짐으로

 

먼저 문제에서 좌표가 무엇을 뜻하는지를 정확하게 읽어야한다

 

"지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다."

 

그러면 (r,c)는 내가 생각하는 좌표로는 (y,x)를 뜻하고 있다

 

그리고 "떨어진 칸의 개수"니까 왼쪽 최상단이 (0,0)이라는 것도 내포하고 있다

 

여기부터 제대로 안읽고 가니까.. 문제가 생겼지

 

"왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다."

 

이것만 보고 나는 왼쪽 방향의 일직선으로 모든 칸을 조사해서, 청소하지 않은 공간이 존재하는지 아닌지

 

하나라도 존재하지 않는건지.. 그런걸 조사했는데

 

"네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다."

 

이걸 보면 바라보는 방향의 바로 1칸이 청소가 가능한건지, 아닌지를 조사하라는 말이라는 걸 알수가 있다

 

아무튼 문제를 이렇게 제대로 이해하고, 조건에 맞게 차례대로 성실하게 구현하자

 

먼저 입력값을 다 받고, 일단 방향 회전이 필요하니까, dictionary로 회전하는 방향을 바로 얻을 수 있도록 해야할 것 같다

 

"바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다."

 

라고 명시했잖아

 

해당 방향을 key로 하고 대응하는 왼쪽 방향을 value로 하는 dictionary를 만들자 

 

n,m = map(int,stdin.readline().split()) 

r,c,d = map(int,stdin.readline().split())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

#청소 했는지 안했는지 여부를 나타내는 배열
clean = [[0]*m for _ in range(n)]

#0:북,1:동,2:남,3:서

delta = [[-1,0],[0,1],[1,0],[0,-1]] 

change_left = {0:3,1:0,2:1,3:2}

 

 

특히 delta배열도 주의해서 만들어야겠다. (r,c)로 명시를 했기때문에.. (y,x)잖아

 

북으로 이동한다는 것은? (-1,0)을 이동한다는 뜻이고

 

남으로 이동한다는 것은? (1,0)을 이동한다는 뜻이다

 

필요한 변수는 만든것 같으니까 문제 조건에 맞게 시뮬레이션 함수를 만들어본다

 

먼저 로봇이 현재 위치를 청소하는데, 청소한 곳은 또 청소하는 것은 아니니까 중복 counting하지 않도록 주의

 

def simulation(r,c,d,change_left,clean,delta,maps):
    
    clean_count = 0

    while 1:
        
        #현재 위치 청소

        if clean[r][c] == 0: #아직 청소하지 않았다면,

            clean[r][c] = 1 #청소했다고 명시하고
            clean_count += 1 #청소한 구역의 수 counting

 

 

이제 현재 위치를 청소했으니까, 현재 방향을 기준으로 왼쪽부터 돌아봐서 청소할 공간이 존재하는지, 아닌지를 조사한다

 

        #왼쪽 방향에 청소할 공간 존재하는지 탐색함

        examine_direction = 0 #어느 방향, 몇번이나 탐색했는지,

        while 1:
            
            examine_direction += 1

            #왼쪽 방향전환

            change_d = change_left[d]
            
            #탐색해보기
            find = search_left(r,c,change_d,n,m,delta,maps,clean)

 

 

이제 왼쪽 방향에 실제로 청소할 공간이 존재하는지, 아닌지를 조사하는 search_left 함수를 만들자

 

from sys import stdin

def search_left(r,c,d,n,m,delta,maps,clean):

    #해당 방향으로 이동해보고
        
    dr = r + delta[d][0]
    dc = c + delta[d][1]
        
    #벽이 아니고, 청소할 공간이 존재한다
    if maps[dr][dc] == 0 and clean[dr][dc] == 0:
        
        return 1
                
    #청소할 공간이 존재하지 않음
    else:
        return 0

 

먼저 방향전환한 방향으로 이동한 좌표를 구하고

 

그 방향에 실제로 벽인지 아닌지 maps[dr][dc]가 0인지 아닌지,

 

maps[dr][dc]가 0이면 벽이 아니고, 그리고 청소할 공간이 존재해야지.. 이미 청소한 곳은 청소하지 않는다 했으니까

 

clean[dr][dc]가 0이어야겠지

 

그런 경우에는 해당 방향에 청소할 공간이 존재하는거니까 1을 return하고

 

이외에는 청소할 공간이 존재하지 않는거니까 0을 return하자

 

그러면 해당 방향을 탐색해봤더니.. 청소할 공간이 존재한다면?

 

            if find == 1: #청소할 공간이 존재함
                
                r = r + delta[change_d][0]
                c = c + delta[change_d][1] #그 방향으로 전진
                d = change_d
                break

 

 

실제 그 방향으로 한칸 전진을 하고, 방향 전환도 해줘야겠지.. d=change_d로 바꿔줘야한다는 것을 까먹지 말자

 

실제로 이동했으니까 반복문을 탈출하고, 청소하러 간다

 

하지만 왼쪽으로 방향전환해서, 찾지 못했고

 

또 왼쪽으로 방향전환해서, 찾지 못하고

 

또 왼쪽으로 방향전환해서 찾지 못하고

 

또 왼쪽으로 방향전환해서 찾지 못한다면?

 

4번을 검사했는데도 찾지 못한다면?

 

            if examine_direction == 4: #모두 청소가 되어 있는 경우
                
                #한칸 후진
                r = r - delta[change_d][0]
                c = c - delta[change_d][1]
                
                examine_direction = 0
            
                if maps[r][c] == 1: #뒤쪽 후진했더니 벽이면..
                    
                    return clean_count #작동 멈추기
                
            d = change_d

 

4방향을 모두 조사했는데도 청소할 공간을 찾지 못했다면, 검사가 끝나고 바라보는 방향을 기준으로 

 

1칸 후진을 한다

 

후진은 빼기를 해주는게 후진이겠지

 

근데 후진을 했는데 maps[r][c]로 넣어보니 그 곳이 벽이라면? 작동을 멈추고 지금까지 센 청소한 구역의 수 clean_count를 return

 

하지만 벽이 아니라면? 해당 방향 d=change_d로 바꿔주고, 다시 왼쪽 방향전환해서 청소할 공간이 존재하는지 아닌지를 반복 탐색

 

당연하지만 새롭게 반복탐색하니까 examine_direction을 0으로 초기화해줘야겠지

 

어려운 부분은 없었고 깔끔하게 성실하게 하면 풀리는 문제였다

 

from sys import stdin

def search_left(r,c,d,n,m,delta,maps,clean):

    #해당 방향으로 이동해보고
        
    dr = r + delta[d][0]
    dc = c + delta[d][1]
        
    #벽이 아니고, 청소할 공간이 존재한다
    if maps[dr][dc] == 0 and clean[dr][dc] == 0:
        
        return 1
                
    #청소할 공간이 존재하지 않음
    else:
        return 0
    

def simulation(r,c,d,change_left,clean,delta,maps):
    
    clean_count = 0

    while 1:
        
        #현재 위치 청소

        if clean[r][c] == 0: #아직 청소하지 않았다면,

            clean[r][c] = 1 #청소했다고 명시하고
            clean_count += 1 #청소한 구역의 수 counting

        #왼쪽 방향에 청소할 공간 존재하는지 탐색함

        examine_direction = 0  #어느 방향, 몇번이나 탐색했는지,

        while 1:
            
            examine_direction += 1

            #왼쪽 방향전환

            change_d = change_left[d]
            
            #탐색해보기
            find = search_left(r,c,change_d,n,m,delta,maps,clean)

            if find == 1: #청소할 공간이 존재함
                
                r = r + delta[change_d][0]
                c = c + delta[change_d][1] #그 방향으로 전진
                d = change_d
                break
        
            if examine_direction == 4: #모두 청소가 되어 있는 경우
                
                #한칸 후진
                r = r - delta[change_d][0]
                c = c - delta[change_d][1]
                
                examine_direction = 0
            
                if maps[r][c] == 1: #뒤쪽 후진했더니 벽이면..
                    
                    return clean_count #작동 멈추기
                
            d = change_d

n,m = map(int,stdin.readline().split())

r,c,d = map(int,stdin.readline().split())

maps = [list(map(int,stdin.readline().split())) for _ in range(n)]

#청소 했는지 안했는지 여부를 나타내는 배열
clean = [[0]*m for _ in range(n)]

#0:북,1:동,2:남,3:서

delta = [[-1,0],[0,1],[1,0],[0,-1]]

change_left = {0:3,1:0,2:1,3:2}

clean_count = simulation(r,c,d,change_left,clean,delta,maps)

print(clean_count)