[백준 17837번] 새로운 게임 2 - python

문제 링크

https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

풀이

구현 문제인데, 너무 어렵다 ㅠㅠ 생각보다 고려해야될 점들이 많은 문제였던 것 같다. 꼭 다시 풀어봐야지... 

 

처음 접근했던 방식은 horse라는 3차원 배열에 위치별 말들을 세워놓고 

where이라는 말의 번호 key, 말들의 위치와 방향을 value 로 기록해두었다. 

그리고 말을 옮길 때마다 갱신해주었는데, 실패했던 이유 중 하나는 현재 말만 옮기는 것이 아니라 다른 말들의 위치도 갱신해줘야하는데 현재 말의 위치만 갱신해주었다는 점이다. 

 

두번째로 주의해야할 점은, 현재 이동하는 말 위치에 있는 모든 말을 옮기는 것이 아니라,

현재 이동하려는 말 위에 있는 말들만 같이 옮겨진다는 점이다. 나는 있는 말들 다 옮겨줘서 계속 마지막 테스트 케이스를 통과하지 못했다. 

 

최종적으로 구현 사항은 다음과 같다. 

horse라는 3차원 배열에 말들 세우기, where라는 배열에 말의 번호 별 위치와 방향 기록하기.

 

그리고 횟수가 1000이 되기 전까지 아래를 반복한다. 

1. 0번 말부터 k-1번 말까지 차례로 방향에 맞게 한칸 이동한다.

2. 이동 위치가 파란색이거나 범위를 벗어난다면 방향을 변경한다. 

여기서 이동 방향 순서가 오른쪽 -> 왼쪽 -> 위 -> 아래로 되어있는데, 

이런 경우 방향을 반대로 해주려면 d ^= 1 로 하면 된다. 알고있으면 코드가 간결해질 수 있다. 

 

만약, 방향을 변경했는데도 위치가 파란색이거나 범위를 벗어난다면 현재 위치를 유지한다.

3. 말의 변경된 이동 위치를 where 에 갱신하고, 만약 제자리라면 다음 말로 넘어간다. 

- 주의해야할 점은, 2번에 의해 반대방향으로 이동했다면 끝나는 것이 아니라 이동 시 색깔에 따라 아래 과정을 또 진행해주어야 한다. 

4. 현재 세워진 말들 중 이동하려는 말이 몇번째인지(index 번호) 구한다.

5. 4번에서 구한 index 위치 뒤에 세워지 말들도 위치를 갱신한다. 

6. 이동하려는 위치가 흰색이라면, index부터 뒤에 있는 말들을 덧붙인다.

7. 이동하려는 위치가 빨간색이라면, index부터 뒤에 있는 말들의 순서를 뒤집어서 덧붙인다. 

8. 현재 위치에서 이동한 말들을 제거한다.

9. 이동 후 말들의 개수가 4개 이상이라면 횟수를 출력하고 중단한다. 

 

n, k = map(int,input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))

horse = [[[] for _ in range(n)]for _ in range(n)]

where = []
for i in range(k):
    x,y,d = map(int,input().split())
    horse[x-1][y-1].append(i)
    where.append((x-1,y-1, d-1))

dx = [0,0,-1,1]
dy = [1,-1,0,0]

cnt = 0

while True :

    if cnt >= 1000:
        print(-1)
        break

    for i in range(k):
        x, y, d = where[i]

        nx = x + dx[d]
        ny = y + dy[d]

        if (nx <0 or nx >= n or ny < 0 or ny >= n) or graph[nx][ny] == 2 :
            # 방향 변경
            d ^= 1

            # 한칸이동
            nx = x + dx[d]
            ny = y + dy[d]

            # 방향 바꾼 후에도 파란색인 경우 이동하지 않음
            if (nx <0 or nx >= n or ny < 0 or ny >= n) or graph[nx][ny] == 2 :
                nx = x
                ny = y

        where[i] = [nx, ny, d]

        if x == nx and y == ny:
            continue

        idx = horse[x][y].index(i)

        for h in horse[x][y][idx+1:]:
            where[h][0] = nx
            where[h][1] = ny

        if graph[nx][ny] == 0 :
            horse[nx][ny] += horse[x][y][idx:]
        if graph[nx][ny] == 1 :
            horse[nx][ny] += horse[x][y][idx:][::-1]

        horse[x][y] = horse[x][y][:idx]

        if len(horse[nx][ny]) > 3 :
            print(cnt+1)
            exit(0)

    cnt += 1