백준 : 로봇 청소기 [삼성 기출, DFS, Gold5, 파이썬]

14503번: 로봇 청소기

문제

입력

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

 

예제 입력

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제 출력 

1

 

 

[문제 풀이]

그냥 시키는 대로 따라가면 되는 DFS 문제였는데.. 이상한 실수를 해서 오래걸렸다.

하하..

 

먼저 DFS로 판단한 기준은 작동을 멈출 때까지 이동하는 거리를 구해야하기 때문이다.

BFS로도 풀리는데 끝까지 가야하니까 DFS가 더 좋을 듯

 

문제를 읽어보면 DFS 코드를 작성할 로직은 다음과 같다.

1) 현재 위치 청소
2) 좌우상하 청소 여부 탐색(꼭 현재를 기준으로 왼쪽부터!) > 안된거 있으면 방문해서 1)로 돌아가 다시 실행
3) 청소할 공간이 없으면 시선 방향 유지한채로 한칸 후진
4) 뒷쪽 방향이 벽이라 후진을 못하면 작동 끝!

여기서 내가 헷갈린 점은 이미 청소된 칸을 방문할 수 없다고 생각했었다. 

> 그래서 방문 처리를 한 칸은 후진을 못하게 코드를 작성했었음

 

또 하나 고려를 못한 점은 상하좌우 청소 여부를 살필 때 순서를 고려하지 않았다.

> 반시계 방향으로 돌면서 탐색하고, 청소 안한칸이 나오면 그쪽으로 방향 바꾸고 전진해야한다.

 

아래가 관련 코드이다.

left = d
for _ in range(4):
	left = (left+3)%4
	x, y = r+dxy[left][0], c+dxy[left][1]

	if (x>=0 and x<n and y>=0 and y<=m):
		if arr[x][y] == 0:
			dfs(x,y,left)
			return

left 변수는 방향 값을 넣는 정수 변수이다. (0 북, 1 동, 2 남, 3 서)

left = (left+3)%4 이 수식으로 반복문을 4번 돌며 현재 기준에서 반시계 방향으로 돌며 청소 여부를 살핀다.

청소를 안했으면 (arr[x][y]==0이면) dfs 문을 호출하고 return한다.

 

또 헷갈린 점은 dfs문이 끝나면 꼭 return을 해주어야한다는 것이다. 

return하지 않으면 또 다시 반복문을 돌며 다른 경우의 수를 구하고 카운트가 된다..

여기서는 정해진 방향대로 가야하기 때문에 모든 경우를 탐색할 필요가 없다.

이 부분이 지금까지 푼 다른 dfs 문이랑 좀 달라서 헷갈렸다. (사실 헷갈릴것도 아니긴 하다.)

 

 

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다. << 이 조건에 관련된 코드이다.

# 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
    if(d==0 and arr[r+1][c]!=1):
            dfs(r+1,c,d)
            return
    if (d==1 and arr[r][c-1]!=1):
            dfs(r,c-1,d)
            return
    if (d==2 and arr[r-1][c]!=1):
            dfs(r-1,c,d)
            return
    if (d==3 and arr[r][c+1]!=1):
            dfs(r,c+1,d)
            return

 

벽일 경우에만 중단함으로 1이 아닐 때 dfs문을 실행한다. (0일 때로 하면 안됨. 0일때로 하면 청소를 한 경우까지 포함이 되어버린다.)

>> 이것때문에 방문처리 값을 2로 주었다.

# 현재 위치 청소
    if arr[r][c]==0: 
        arr[r][c] = 2 # 방문처리 값 = 2, 벽일때는 = 1
        answer+=1

 

남이 작성한 후진하는 코드는 훨씬 간결했다

bx, by = r - dxy[left][0], c - dxy[left][1]

if arr[bx][by] != 1:
	dfs(bx, by, left)

 

인덱스를 먼저 설정하고 재귀함수를 호출하는데,

습관이 들어서 자꾸 노가다로 상하좌우 코드 모두 작성하게된다.

연습해야겠다..

 

[전체 코드]

n,m = map(int, input().split())
r,c,d = map(int, input().split()) # 좌표,방향
arr = [list(map(int, input().split())) for _ in range(n)]
answer = 0
# 북동남서
dxy = [(-1, 0), (0, 1), (1, 0), (0, -1)]

# 0 북, 1 동, 2 남, 3 서
def dfs(r, c, d):
    global answer
    # 현재 위치 청소
    if arr[r][c]==0:
        arr[r][c] = 2
        answer+=1

    left = d
    for _ in range(4):
        left = (left+3)%4
        x, y = r+dxy[left][0], c+dxy[left][1]

        if (x>=0 and x<n and y>=0 and y<=m):
            if arr[x][y] == 0:
                dfs(x,y,left)
                return

    # 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
    if(d==0 and arr[r+1][c]!=1):
            dfs(r+1,c,d)
            return
    if (d==1 and arr[r][c-1]!=1):
            dfs(r,c-1,d)
            return
    if (d==2 and arr[r-1][c]!=1):
            dfs(r-1,c,d)
            return
    if (d==3 and arr[r][c+1]!=1):
            dfs(r,c+1,d)
            return

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

 

더 짧게 작성한 코드

# 0 북, 1 동, 2 남, 3 서
def dfs(r, c, d):
    global answer
    # 현재 위치 청소
    if arr[r][c]==0:
        arr[r][c] = 2
        answer+=1

    left = d
    for _ in range(4):
        left = (left+3)%4
        x, y = r+dxy[left][0], c+dxy[left][1]

        if (x>=0 and x<n and y>=0 and y<=m):
            if arr[x][y] == 0:
                dfs(x,y,left)
                return
    bx, by = r - dxy[left][0], c - dxy[left][1]

    if arr[bx][by] != 1:
        dfs(bx, by, left)


n,m = map(int, input().split())
r,c,d = map(int, input().split()) # 좌표,방향
arr = [list(map(int, input().split())) for _ in range(n)]
answer = 0
# 북동남서
dxy = [(-1, 0), (0, 1), (1, 0), (0, -1)]

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