[TIL_Carrotww] 112 - 23/05/11

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 로봇

오랜만에 올리는 것 같다 매일 쓴다고 해놓고서...
일산에서 선롱까지(소마 센터) 왔다 갔다 하다보면 알고리즘은 풀어도 기록하면서 코멘트를 달기가 쉽지 않다 ㅠ

기획심의를 통과 못하면 다음 기획 심의는 다음달이고 720만원인가 지원금을 한달동안 못 사용한다고 하니 여간 골치아픈일이 아닐 수 없다.
해서 소마에 신경을 조금 쓰느라.. 못쓰고있다.. 라고 핑계를..ㅎㅎ
그래도 쓰는 이유는 이 문제 푸는데 시간이 반나절이나 걸려서 빡쳐서 기록하고 가려고 한다.

• 내 풀이

def solve():
    import sys
    from collections import deque

    row, col = map(int, sys.stdin.readline().split())
    # 0 -> 동, 1 -> 서, 2 -> 남, 3 -> 북
    dr, dc = [0, 0, 1, -1], [1, -1, 0, 0]
    change_direct = [[2, 3], [2, 3], [0, 1], [0, 1]]
    visited = [[[0]*4 for _ in range(col)] for _ in range(row)]
    graph = []

    for _ in range(row):
        graph.append(list(map(int, sys.stdin.readline().split())))

    start_r, start_c, start_direct = map(lambda x:int(x)-1, sys.stdin.readline().split())
    end_r, end_c, end_direct = map(lambda x:int(x)-1, sys.stdin.readline().split())
    visited[start_r][start_c][start_direct] = 1

    queue = deque()
    queue.append([start_r, start_c, start_direct, 0])

    while queue:
        cur_r, cur_c, cur_direct, cnt = queue.popleft()
        if cur_r == end_r and cur_c == end_c and cur_direct == end_direct:
            print(cnt)
            break

        for k in range(1, 4):
            n_d = cur_direct
            n_r, n_c = dr[n_d]*k + cur_r, dc[n_d]*k + cur_c
            if (n_r < 0 or n_r >= row) or (n_c < 0 or n_c >= col) or graph[n_r][n_c] == 1:
                break
            if visited[n_r][n_c][cur_direct] == 1:
                continue
            queue.append([n_r, n_c, n_d, cnt+1])
            visited[n_r][n_c][n_d] = 1

        for n_direct in change_direct[cur_direct]:
            if visited[cur_r][cur_c][n_direct] == 1:
                continue
            queue.append([cur_r, cur_c, n_direct, cnt+1])
            visited[cur_r][cur_c][n_direct] = 1

if __name__ == "__main__":
    solve()

일단 첫 번째 포인트
1. visited 체크를 해줄때 해당 좌표에서 동서남북을 바라보는 상태를 기록해줘야 하기 때문에 3차원 배열을 사용해야한다.
여기까지는 생각했다 많이 풀어봤어서...
하지만 일단 풀어보자 해서 2차원 배열로 풀었고 정답이 나오지 않았다. 다른 이유였지만 이것때문에 안됐는지는 테스트 해봐야된다. 아마 3차원으로 해야 되지 않을까 싶다. 모든 방향으로 전환 가능한게 아니기 때문에

visited = [[[0]*4 for _ in range(col)] for _ in range(row)]

2. 처음에는 지금처럼 코드가 이쁘지 않았다. 방향 전환함에 있어서 문제를 대충 읽고 풀어서 모든 방향으로 전환 가능하게 해줬다.
   근데 이렇게 해도 상관이 없을 것 같은게 visited를 결국 체크해주기 때문에 queue에 쓸데없는게 조금씩 쌓이기는 하겠지만 조건 처리만 잘 해주면 결국 ok 일 것같다.
   하지만 직관적이지 않아서 바꿨다.

3. 벽을 뚫고 가는 경우

if (n_r < 0 or n_r >= row) or (n_c < 0 or n_c >= col) or graph[n_r][n_c] == 1:
	break
if visited[n_r][n_c][cur_direct] == 1:
	continue
queue.append([n_r, n_c, n_d, cnt+1])
visited[n_r][n_c][n_d] = 1

위 코드와

if (n_r < 0 or n_r >= row) or (n_c < 0 or n_c >= col) or graph[n_r][n_c] == 1 or visited[n_r][n_c][cur_direct] == 1:
	continue
queue.append([n_r, n_c, n_d, cnt+1])
visited[n_r][n_c][n_d] = 1

아래 코드의 다른점을 바로 알면 당신은 나보다 천재
습관처럼 한줄로 if문에 조건을 쫙 써줬지만 계속 정답이 안 나와서 생각을 해보니 첫 번째 벽 즉 graph에서 1을 만나면 그 다음 두 번째 칸도 이동할 수 없다. 그렇게되면 벽을 만나자마자 바로 break를 걸어서 for문을 나와야한다.
다음 for문에서 벽을 뛰어넘고 큐에 추가될 수 있기 때문에. 위 코드때문에 안됐었는데 다른 코드만 주구장창 고치고 있었다 ㅠㅜㅠ
이 문제 때문에 잠을 못잔게 짜증나서 이렇게 기록을 해둔다...ㅎ

오늘.. 끝!