BAEKJOON 14503

22 Apr 2020

문제

입력

—–

나의 처음 코드

이 문제를 보자마자 왜인지 dfs 냄새가 났지만, bfs로 해결할 수 있을 것 같다는 생각에 시간을 좀 낭비했다. 어찌됐건간에 dfs, bfs문제 둘다 아닌거로 시간낭비를 오~지게 했다. 로봇이 움직이는 조건이 계속 읽어봐도 이해가 가지 않아서 나중에는 dfs로 풀다가 계속 두번째 테케에서 59가 나오길래,,, 왜 자꾸 59가 나오는것이여어어어어 했는데, 알고보니 로봇은 이렇게 움직인다 4방향이 다 막혀있을 때, 자기를 부른(재귀call을 한)곳으로 가는게 아니라, 자기가 보고있는 방향의 반대방향으로 가는것이다. 이말 즉슨, 얼핏보면 call한곳으로 돌아가는 것처럼 보이지만, 아닐 수도 있다는 것이다. 저 문장을 읽으면 dfs로 푸는 여러분 또한 엥? 하고 바로 풀 것이다. (나만 그런 거일수도 ㅎㅎ) 코드는 다음과 같다.

N, M = list(map(int, input().split()))
now_info = list(map(int, input().split()))
map_list = []

for i in range(N):
    map_list.append(list(map(int, input().split())))

rl_list = [0,1,0,-1]
ud_list = [-1,0,1,0]
count = 0

def dfs(now_coord):
    global count
    x, y, direct = now_coord
    count += 1
    map_list[x][y] = 2 #방문한곳 청소완료 == 2
    
    i = 1
    #총 4개의 방향
    while i != 5:
        #방향 잡아주기
        tmp_dir = direct - i
        if tmp_dir < 0:
            tmp_dir = 4 - abs(tmp_dir)
        
        tmp_x = x + ud_list[tmp_dir]
        tmp_y = y + rl_list[tmp_dir]
        i += 1
        
        #청소할 곳이 청소가 되어있지 않다면
        if map_list[tmp_x][tmp_y] == 0:
            flag = dfs((tmp_x, tmp_y, tmp_dir))
            if flag == (0,0,0):
                return (0,0,0)
            else:
                x, y, direct = flag
                i = 1
                
    #반대 방향 계산해주기
    if direct == 0:
        tmp_x =  x + 1
        tmp_y = y
    elif direct == 1:
        tmp_x = x
        tmp_y = y - 1        
    elif direct == 2:
        tmp_x = x - 1
        tmp_y = y
    else:
        tmp_x = x
        tmp_y = y + 1
    
    if map_list[tmp_x][tmp_y] == 1:
        #빠꾸해도 벽이여서 못갈 때
        return (0,0,0)
    else:
        #빠꾸하면 갈 수 있을 때
        return (tmp_x, tmp_y, direct)
    
dfs(tuple(now_info))
print(count)
#     

이것도 맞는 결과지만, dfs를 안쓰고 while문으로 쓰면 시간이 2배나 단축된다. 그 코드는 다음과 같다. 다음 코드는 내가 다시 짜기 귀찮아서,,,, 다른 사람이 짜놓은 코드를 가지고 온 것이다. 내것이 dfs로 헛짓 한거 빼면은 같은 맥락상에 있는 코드이다.

개선된 코드

# 방향은 북동남서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 방향 바꿔주기
def change(d):
    if(d == 0):
        return 3
    elif(d == 1):
        return 0
    elif(d == 2):
        return 1
    elif(d == 3):
        return 2

def find(r,c,d):
    cnt = 1
    x = r
    y = c
    arr[x][y] = 2 
    while(True):
        dc = d
        for i in range(4):
            empty = 0
            dc = change(dc)
            nx = x + dx[dc]
            ny = y + dy[dc]
            # 유효 범위 안에 있고, 빈칸이라면
            if(0<=nx<n and 0<=ny<m and arr[nx][ny] == 0):
                cnt += 1
                x = nx
                y = ny
                arr[nx][ny] = 2
                d = dc
                empty = 1
                break
        # 4방향 모두 탐색 후 모든 칸이 청소가 되었다면
        if(empty == 0):
            # 후진
            if(d == 0):
                x += 1
            elif(d == 1):
                y -= 1
            elif(d == 2):
                x -= 1
            elif(d == 3):
                y += 1
            # 후진하려는 칸이 벽이라면 stop
            if(arr[x][y] == 1):
                break
    return cnt

n, m = map(int, input().split())
r, c, d = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
res = find(r,c,d)
print(res)      

문제를 잘 읽어봐야한다,,, 나는 사실 하울의 움직이는 성 보면서 풀어가지고 이 사단이 난 것이다…. 하하