[백준]17837.새로운게임2

문제 설명

오랜만에 구현문제를 접했고, 좀 빡쎘다. ㅎㅎ; 설명한대로 구현하면 되서 100% 구현이라 봐도 무방하다.

문제는 지문 그대로 이해하면 되고, 구현시 주의해야할 사항은 다음과 같다.

• 1번 말부터 순서대로 이동시킨다.(말의 이동순서가 결과에 영향을 미침)
• 말의 이동방향이 파란색 or 벽일 경우.
  • 이동 방향을 반대로 한 뒤, 1칸 이동할 때 파란색이면 그대로 멈추기.
  • 빨간색이거나 흰색일 경우 빨간색or흰색일 경우를 그대로 적용! (난 이 부분에서 헤맸다. 말만 그대로 이동시킴.)

문제 접근

접근은 큰 흐름을 고려한 뒤 구체적인 부분을 해결하는 방식으로 접근했다.

i)전체적인 흐름

1. 턴의 횟수를 1 증가시킨다.
2. 말을 선택한다.
3. 말의 다음 위치의 타일을 확인한다.
4. 다음 위치의 타일의 색에 맞도록 말을 이동시킨다.
5. 말을 모두 선택할 때 까지 2~4과정을 반복한다.
6. 턴의 횟수가 1000이 넘거나 움직인 위치에 말의 수가 4이상이 될 때까지 1~5과정을 반복한다.

이런 흐름으로 작성한다면 문제없다.

ii)주요 변수들

말

말이란 클래스는 다음과 같다.

• 이동방향, y,x 위치 좌표를 가지고 있다.(특징)
• 이동한다는 행동을 가지고 있다.

말을 순서대로 이동시키기 위해 horseList에 객체인 말을 담았다.(python에서 객체도 리스트에 담을 수 있다.)

체스판(테이블)

테이블은 구조체처럼 생각하여 table[r][c]의 원소는 [color,horses,count]가 되겠다.

• color : int타입으로 타일의 색을 의미 3일 경우 벽이라고 정함
• horses : list타입으로 해당 타일에 있는 말 객체를 담았다. 스택 자료형으로 생각했다.(스택으로 놓은 이유는 아래에 설명하겠음)
• count : int타입으로 해당 위치에 말이 얼마나 있는지 나타낸다. 4이상인지 체크할 때 sum안 쓰려고 작성한 것.(이부분은 차라리 변수를 없애고 sum을 하는게 나았을 수 있겠다.)

체스말의 다음 위치가 벽일 경우를 간단하게 처리하기 위해 외벽을 만들어주었다. color는 3으로 지정하여 벽임을 구분하였다.

iii)주요 행동?모듈?들

말 A의 다음 이동위치의 타일이 빨간색일 경우 이동방식은 다음과 같다.

말A의 현재 위치 horses에서 A가 나올 때까지

• pop하여 해당 말을 다음 위치에 이동시킨다. 이때 현재 위치 count -1, 다음 위치 count +1 도 해준다!

stack자료구조였으므로 다음 위치엔 역순으로 쌓이게 된다.

말 A의 다음 이동 위치의 타일이 흰색일 경우는 다음과 같다.

위처럼 horsese에서 A가 나올 때까지 pop해주나 바로 다음 위치에 삽입하지말고 임시 Stack자료구조에 담는다.

그 임시 자료구조에서 다시 팝하여 다음 위치에 넣어준다.

이렇게 하면 원래 순서대로 쌓이게 된다.

위를 봤을 때 horses의 자료구조를 스택으로 선언한 이유는 다음과 같다.

​ 1.큐로 선언할 경우 원형 큐로 만들어주어야 값 재정렬에 시간 자원을 사용하지 않을 수 있다. 그런데 원형큐 만들기 번거로워서 스택구조로 선언했다.

 2. 면접에서 스택2개와 큐에 대한 질문을 받아본 적이 있어서 위 처럼 구현했다.

iv)위 처럼 말을 구현시 문제점

객체지향으로 접근하여 말을 구현한다고 했다. 그런데 작성하다가 엄청난 문제점이 생겼다. 최근 edwidth에서 배운 scope에 대한 관점으로 문제를 분석해보겠다.

말A는 현재 위치에 다른 말이 있는지 모른다. 말 A보다 상위에 있는 객체가 말A의 위치와 말 A의 위치에 있는 다른 말들의 정보를 알수가 있다. 물론 말 A가 Table과 상호작용하여 A가 정보를 알 수 있다 하더라도,

말 A가 다른 말들을 이동시킨다고 하면 이상해진다. 말 A와 말 B는 동등한 객체인데 말 B를 이동시킨다니... 말 A보다 상위의 객체가 말A를 포함하여 말 A가 있는 위치에 있는 다른 말들을 옮긴다고 보는게 더욱 합당하다.

위와 같은 이유, 파란색 타일일 때 이동할 경우를 잘못 생각해서 코드가 꽤나 복잡해졌다.

한편, 모든 객체들의 정보를 알고 행동시키게 하는 존재는 누구일까 생각해보니 그게 바로 main이 아닌가...?란 생각이 들었다. 여튼, 이 문제는 더욱 명료하게 작성할 수 있지만 못해서 아쉬움이 남는다.

또 한편으로 내가 객체를 수직적 관계로만 생각하여 접근했나 싶기도 하다.

구현

import sys
input = sys.stdin.readline
direction = [[0,0],[0,1],[0,-1],[-1,0],[1,0]]
class Horse:
    def __init__(self,r,c,d):
        self.r = r
        self.c = c
        self.d = d

def turnDirect(d):
    if d == 1:
        return 2
    if d == 2:
        return 1
    if d == 3:
        return 4
    else:
        return 3

N,K = map(int,input().split())

#테이블 생성
table = [[[3,[],0] for _ in range(N+2)] for _ in range(N+2)] #벽 고려해서 생성

for r in range(1,N+1):
    colors = tuple(map(int,input().split()))
    for i in range(1,N+1):
        table[r][i][0] = colors[i-1]

horseList = []
for _ in range(K):
    r,c,d = map(int,input().split())
    h = Horse(r,c,d)
    horseList.append(h)
    table[r][c][1].append(h)
    table[r][c][2] += 1

t = 0
flag = False
while t<=1000:
    t += 1
    for i in range(K):
        h = horseList[i]
        nr,nc = h.r+direction[h.d][0] ,h.c+direction[h.d][1]

        if table[nr][nc][0] == 0:
            curHorse = table[h.r][h.c][1].pop()
            table[h.r][h.c][2] -= 1
            tempStack = [curHorse]

            while h != curHorse:
                curHorse = table[h.r][h.c][1].pop()
                tempStack.append(curHorse)
                table[h.r][h.c][2] -= 1

            while tempStack:
                moveHorse = tempStack.pop()
                moveHorse.r,moveHorse.c = nr,nc
                table[nr][nc][1].append(moveHorse)
                table[nr][nc][2] += 1

        elif table[nr][nc][0] == 1:
            curHorse = table[h.r][h.c][1].pop()
            table[nr][nc][1].append(curHorse)
            table[h.r][h.c][2] -= 1
            table[nr][nc][2] += 1
            curHorse.r,curHorse.c = nr,nc
            while h != curHorse:
                curHorse = table[h.r][h.c][1].pop()
                table[nr][nc][1].append(curHorse)
                table[h.r][h.c][2] -= 1
                table[nr][nc][2] += 1
                curHorse.r, curHorse.c = nr, nc

        else:
            # 방향 바꾸기
            h.d = turnDirect(h.d)
            nr,nc = h.r + direction[h.d][0],h.c +direction[h.d][1]

            if table[nr][nc][0] == 2 or table[nr][nc][0] == 3:
                pass
            else:
                if table[nr][nc][0] == 0:
                    curHorse = table[h.r][h.c][1].pop()
                    table[h.r][h.c][2] -= 1
                    tempStack = [curHorse]

                    while h != curHorse:
                        curHorse = table[h.r][h.c][1].pop()
                        tempStack.append(curHorse)
                        table[h.r][h.c][2] -= 1

                    while tempStack:
                        moveHorse = tempStack.pop()
                        moveHorse.r, moveHorse.c = nr, nc
                        table[nr][nc][1].append(moveHorse)
                        table[nr][nc][2] += 1

                elif table[nr][nc][0] == 1:
                    curHorse = table[h.r][h.c][1].pop()
                    table[nr][nc][1].append(curHorse)
                    table[h.r][h.c][2] -= 1
                    table[nr][nc][2] += 1
                    curHorse.r, curHorse.c = nr, nc
                    while h != curHorse:
                        curHorse = table[h.r][h.c][1].pop()
                        table[nr][nc][1].append(curHorse)
                        table[h.r][h.c][2] -= 1
                        table[nr][nc][2] += 1
                        curHorse.r, curHorse.c = nr, nc

        if table[h.r][h.c][2]>=4:
            flag = True
            break

    if flag:
        break


if flag:
    print(t)
else:
    print(-1)