[백준 14503번] 로봇 청소기

n,m = map(int,input().split())

r,c,d = map(int,input().split())

# 현재 방향을 기준으로 반시계방향으로 탐색
dx = [[0,1,0,-1],[-1,0,1,0],[0,-1,0,1],[1,0,-1,0]]
dy = [[-1,0,1,0],[0,-1,0,1], [1,0,-1,0],[0,1,0,-1]]

# 바라보는 방향이 북쪽인 경우
# dx_0 =[0,1,0,-1]
# dy_0 =[-1,0,1,0]

# 바라보는 방향이 동쪽인 경우
# dx_1 = [-1,0,1,0]
# dy_1 = [0,-1,0,1]

# 바라보는 방향이 남쪽인 경우
# dx_2 = [0,-1,0,1]
# dy_2 = [1,0,-1,0]

# 바라보는 방향이 서쪽인 경우
# dx_3 = [1,0,-1,0]
# dy_3 = [0,1,0,-1]

status = [list(map(int,input().split())) for _ in range(n)] # 방 상태
visited = [[False]*m for _ in range(n)] # 방문 여부

global count
count = 0

def dfs(x,y,direction):
    global count

    has_empty = False # 빈칸 존재 여부

    if not visited[x][y]: # 처음 방문했을 경우에만 방문 처리 및 카운팅
        visited[x][y] = True
        count += 1

    for i in range(4):
        nx = x + dx[direction][i]
        ny = y + dy[direction][i]
        
        if status[nx][ny] != 1 and not visited[nx][ny]: # 벽이 아니고 청소가 아직 이루어지지 않은 경우
            if dx[direction][i] == 0 and dy[direction][i] == 1:
                temp_d = 1
            elif dx[direction][i] == 0 and dy[direction][i] == -1:
                temp_d = 3
            elif dx[direction][i] == 1 and dy[direction][i] == 0:
                temp_d = 2
            elif dx[direction][i] == -1 and dy[direction][i] == 0:
                temp_d = 0
            has_empty = True
            dfs(nx,ny,temp_d)
            break # 로봇 청소기가 빈칸을 찾고 경로를 선택했기 때문에 탐색 중단

    if not has_empty: # 빈칸이 없는 경우
        opposite_direction = (direction+2)%4 # 후진 방향 설정
        opposite_x = x + dx[opposite_direction][3] # 후진한 x좌표
        opposite_y = y + dy[opposite_direction][3] # 후진한 y좌표
        
        if status[opposite_x][opposite_y] == 1: # 후진한 좌표가 벽일 경우 종료
            return
        else: # 벽이 아니라면 방향을 유지하면서 후진
            dfs(opposite_x,opposite_y,direction)

dfs(r,c,d)
print(count)

이번 문제는 이전에 도전했다가 실패했던 문제 중 하나인 문제로, 주어진 조건에 맞게 로봇 청소기를 작동시켰을 때 최종적으로 청소한 영역의 개수를 구하는 문제이다.

 

일단 문제의 조건에 따르면 현재 위치에서 반시계방향으로 회전해가며 빈칸을 탐색해야 하기 때문에 각각의 위치(0,1,2,3)에 따라 다르게 dx,dy를 설정해주었다.(상하좌우 탐색을 위한 좌표 값)

 

빈칸이 존재하는 경우에는 해당 위치(nx,ny)로 전진하고 방향(temp_d)을 전달해주었고, 빈칸이 존재하지 않는다면 후진 가능 여부를 체크하고 후진이 가능할 경우에는 방향을 유지한 채로 후진해주었다.

 

하지만 자꾸 테스트케이스에서 청소하지 말아야 할 구역까지 청소를 해서 1시간동안 골머리를 앓았는데, 생각해보니 DFS나 BFS 알고리즘의 특성상 모든 경로를 탐색해보기 때문에 이 문제의 경우에는 경로를 선택하고 나서는 반복문을 멈춰주어야 한다 ⭐️⭐️⭐️⭐️

 

위 조건을 떠올리고 코드를 수정한 결과 곧바로 문제를 해결할 수 있었다. 구현 능력을 기를 수 이었던 좋은 문제였다 :)