20210422

코딩테스트 대비해서 아래 DFS, BFS 추천 문제 다 풀어보고 있다.

(방금 성곽을 풀고 왔는데, 캐슬디펜스 왜 43프로인지 모를 일..)

다이어리에 백준 20프로대 문제들 다 풀어볼 것이라고 적어놨는데, 코테풀기 시작하고 한 3시간 지났는데 왜 아직 캐슬디펜스만 푼 건지도 모를 일..

로봇 풀다 말았다.

현 상황은 다음과 같다.

import sys
from collections import deque
input = sys.stdin.readline

m, n = map(int, input().split())
m_ap = [list(map(int, input().split())) for _ in range(m)]
s1, s2, sd = map(int, input().split())
e1, e2, ed = map(int, input().split())
# east - 1, west - 2, south - 3, north - 4
# east left - north, east right - south
# west left - south, west right - north
# south left - west, south right - east
# north left - east, north right - west

dir = dict()
dir[1] = (4, 3) # east
dir[2] = (3, 4) # west
dir[3] = (2, 1) # south
dir[4] = (1, 2) # north
ddd = [0, 1, -1, 1, -1]
# 2 types of commands 
# go using 'xd'
# chang 'xd'

q = deque([[sd, s1-1, s2-1]])
# visited + change direction at that location
dvisited = [[[-1] * n for _ in range(m)] for __ in range(5)]
dvisited[sd][s1-1][s2-1] = 0

while q:
    _d, _x, _y = q.popleft()
    
    if _x == e1 - 1 and _y == e2 - 1 and _d == ed:
        print("dvisited[",_d,"][",_x, "][", _y,"]=",dvisited[_d][_x][_y])
        break

    print("_d:", _d, ", _x:", _x, ", _y:", _y)
    for dd in dir[_d]:
        if dvisited[dd][_x][_y] != -1: continue
        dvisited[dd][_x][_y] = dvisited[_d][_x][_y] + 1
        q.append([dd, _x, _y])
        print("dvisited[",dd,"][",_x, "][", _y,"]=", dvisited[dd][_x][_y])
        
    x, y, d = _x, _y, _d
    for a in range(1, 4):
        if d == 1 or d == 2: # east or west
            # _y + -1 * n or _y + (1 * n)
            y = _y + ddd[d] * a
        else: # north or south
            # _x + -1 * n or _x + (1 * n)
            x = _x + ddd[d] * a
        
        if x < 0 or y < 0 or x >= m or y >= n: continue
        if m_ap[x][y] == 1: continue
        if dvisited[d][x][y] != -1: continue
        dvisited[d][x][y] = dvisited[_d][_x][_y] + 1
        q.append([d, x, y])
    print(q)
for i in range(1, 5):
    for j in range(m):
        print(dvisited[i][j])
    print()

물론 답은 나오지 않는다.. 일단 코드가 너무 복잡해졌다.

1. 오른쪽, 왼쪽 회전이 가능하기 때문에 동, 서, 남, 북 각각의 회전 후 상태를 딕셔너리로 저장하였다.
2. dvisited라는 방문 배열을 선언해서 해당 위치를 방문했는지를 확인할 뿐만 아니라 해당 위치에 어느 쪽을 보고 서 있는지도 체크하고 있다.
3. ddd라는 배열을 통해서 동, 서, 남, 북 방향에 따라 어떻게 이동할 지를 결정한다.
4. 조건 성립 시, 큐에 넣는다.

모르겠다.. 팀플하러가야징..