우선 처음 문제를 봤을때 어? 그냥 DFS나 BFS로 풀면 되는거 아닌가? 라고 생각했다. 하지만 문제에서 주어진 예제와 요구사항을 보니 그게 아니었다.
문제에서 요구하는 것은 로봇청소기가 멈췄을때의 청소한 칸의 개수였다.
로봇청소기가 멈추는 상황은 딱 하나다.
2-2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
따라서 단순한 DFS, BFS문제가 아닌것을 확인하고 다른 방법으로 풀어야한다고 생각했다.
근데 사실 문제에서 풀이방법을 제시해주고 있었던 것 같다.
세세하게 조건을 나눠서 알려줘서 그대로 구현하면 큰 문제가 없었다.
아래는 제출한 코드이다.
import sys
N,M = map(int, sys.stdin.readline().split())
x,y,d_index = map(int, sys.stdin.readline().split())
pan = []
for i in range(N):
pan.append(list(map(int,sys.stdin.readline().split())))
direction = [[-1,0],[0,1],[1,0],[0,-1]] #북, 동, 남, 서
def go(i,j,d):
global count
# if i<0 or j<0 or i>(N-1) or j>(M-1):
# return
if pan[i][j]==0: #현재칸이 청소되지 않았다면 청소한다.
pan[i][j]=2
count += 1
#현재칸의 주변 4칸을 둘러보고 청소되지 않은 칸이 있다면 반시계방향으로 90도 회전하고 앞쪽칸이 청소되지 않은 빈칸이라면 전진하여 반복.
if ifcleanaround(i,j):
for k in range(4):
d-=1
if d<0:
d+=4
ni = i+direction[d][0]
nj = j+direction[d][1]
if pan[ni][nj]==0:
break
go(ni,nj,d)
#주변 4칸중에 청소되지 않은 칸이 없다면
else:
ni = i-direction[d][0] #후진
nj = j-direction[d][1]
if pan[ni][nj]==1: #후진했을때 벽이라면 종료
return
go(ni,nj,d)
def ifcleanaround(i,j):
for k in range(4):
ni = i+direction[k][0]
nj = j+direction[k][1]
if ni>=0 and nj>=0 and ni<=(N-1) and nj<=(M-1):
if pan[ni][nj]==0:
return True #청소되지 않은 칸이 있을때
return False #청소되지 않은 칸이 없을때
count = 0
go(x,y,d_index)
print(count)
def ifcleanaround(i,j): for k in range(4): ni = i+direction[k][0] nj = j+direction[k][1] if ni>=0 and nj>=0 and ni<=(N-1) and nj<=(M-1): if pan[ni][nj]==0: return True #청소되지 않은 칸이 있을때 return False #청소되지 않은 칸이 없을때이 함수는 주변에 청소가능한 칸이 있는지를 검사하는 함수이다.
따라서 처음부터 코드를 보자면
우선 처음 실행시에 현재 칸이 청소가 되어있는지를 확인하고 안되어있다면 현재칸을 청소(2로변환)한다.
그리고 ifcleanaround함수를 사용하여 주변에 청소가능한 칸이 있는지를 확인한다. 만약 청소가능한 칸이 있다면 방향을 현재방향에서 90도 변경하고 앞칸이 청소되어있는지를 확인하고 청소되어있지 않다면 go()함수를 실행한다. 인수로는 그 앞칸의 인덱스와 현재의 방향을 넣어준다.
만약 청소가능한 칸이 없다면 한칸 후진해야하는데 후진했을 때 벽이라면(1이라면) return을 통해 함수를 종료해준다. 하지만 벽이 아니라면 그대로 한칸 후진한다.
