[백준 17837번] 새로운 게임2(파이썬)

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

17837번: 새로운 게임 2

이 문제는

하얀색과 빨간색

두 개를 이동할 때 어떻게 구현할 것인가가

큰 관문이었습니다.

저는 저런식으로

알고리즘을 구성해봤습니다.

이 풀이방법은

list배열의 위치를 받아

기존 위치는 pop을 해주는 방식입니다.

 

# 백준 17837번 새로운 게임2

N, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[[] * N for _ in range(N)] for _ in range(N)]

keys = []
for i in range(K):
    a, b, d = map(int, input().split())
    keys.append([a - 1, b - 1, d - 1])
    visited[a - 1][b - 1].append(i)
# visited에 현재 말의 요소값에 말을 append하고 얼마나 쌓여있는지 본다.
# 방향 우 좌 상 하
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

turn = 1


def white(x, y, nx, ny, k):
    global keys
    tmp = []
    tmp_index = visited[x][y].index(k)
    tmp_len = len(visited[x][y])
    # white로 움직일 때 현재 키의 index를 구함
    # (ex visited[x][y] 에 1 2 3 4 이렇게 있고, 2를 움직인다하면 2의 index를 구함
    # 그 다음 2와 그 위의 인수들을 나열한다
    # tmp에 받은 후에 넘길 예정.
    while len(tmp) != tmp_len - tmp_index:
        tmp_sort = visited[x][y].pop(tmp_index)
        tmp.append(tmp_sort)
    for nk in tmp:
        visited[nx][ny].append(nk)
        keys[nk][0] = nx
        keys[nk][1] = ny
    # print("v")
    # print(visited)
    # print("k")
    # print(keys)


def red(x, y, nx, ny, k):
    global keys
    tmp = []
    tmp_index = visited[x][y].index(k)
    tmp_len = len(visited[x][y])
    while len(tmp) != tmp_len - tmp_index:
        tmp_sort = visited[x][y].pop(tmp_index)
        tmp.append(tmp_sort)
    tmp.reverse()

    for nk in tmp:
        visited[nx][ny].append(nk)
        keys[nk][0] = nx
        keys[nk][1] = ny
    # print("v")
    # print(visited)
    # print("k")
    # print(keys)


def blue(x, y, d, k):
    if d == 0:
        d = 1
    elif d == 1:
        d = 0
    elif d == 2:
        d = 3
    else:
        d = 2
    ny = y + dy[d]
    nx = x + dx[d]
    # print(ny,nx)
    keys[k][2] = d
    if (nx < 0 or nx >= N) or (ny < 0 or ny >= N):
        return

    if graph[nx][ny] == 0:
        # print("w")
        white(x, y, nx, ny, k)
    if graph[nx][ny] == 1:
        # print("r")
        red(x, y, nx, ny, k)
    if graph[nx][ny] == 2:
        # print("end")
        return


while turn <= 1000:
    out = 0
    # print(keys)
    # print(visited)
    # 각 말을 차례대로 움직인다.
    for i in range(K):
        # print(i)
        x = keys[i][0]
        y = keys[i][1]
        d = keys[i][2]
        ny = y + dy[d]
        nx = x + dx[d]
        # print(ny,nx)
        if (nx < 0 or nx >= N) or (ny < 0 or ny >= N):
            # print("out")
            blue(x, y, d, i)
        else:
            if graph[nx][ny] == 0:
                # print("white")
                white(x, y, nx, ny, i)
            if graph[nx][ny] == 1:
                # print("red")
                red(x, y, nx, ny, i)
            if graph[nx][ny] == 2:
                # print("blue")
                blue(x, y, d, i)
        # 이동할 때 마다 말의 갯수 확인
        final_flag = 0
        for i in range(N):
            flag = 0
            for j in range(N):
                if len(visited[i][j]) >= 4:  # 범위...틀리지 말자....
                    flag = 1
                    break
            if flag == 1:
                # print("break")
                final_flag = 1
                break
        if final_flag == 1:
            out = 1
            break

    if out == 1:
        break

    turn += 1

    # print()
    # print(turn)
if turn > 1000:
    print(-1)
else:
    print(turn)

 

이 문제는 풀이는 한 시간만에 다 풀었는데

제출 후 92%에서 틀렸다고 떠서

상당히 분노했던 문제입니다.

분명히 난 맞았는데...

그렇게 계속 해매다가

솔루션과 비교해도

'나랑 똑같은데 뭐가 다른거야!'

라면서 화를 냈습니다.

그러다 백준 질문게시판에

저처럼 92%에서 좌절하시는 분의 질문을 보고

4일 때 빠져나갔던 걸

4이상일 때 빠져나가는 걸로 개선했습니다.

그러니 풀렸습니다...

이게 무슨 황당한 케이스가 다있나 싶어서

문제를 자세히 읽어보니

라고 되어있었습니다.

즉, 친절하게

'4랑 같거나 큰 경우를 구하세요'

라고 적혀있었네요.

저걸 다시보니

좀 어이가 없기도 하고

화도 나기도 했습니다.

하지만 문제에서는

분명 '4이상'으로 되어있었습니다.

이건 문제를 잘못 읽은 저의 문제...

알고리즘 구현도 중요하지만

범위에 대한 부분도 엄청 중요함을 많이 깨달았습니다.

이제 문제 풀 때

범위나오면 노트에 적고 시작하자....

https://chldkato.tistory.com/130

백준 17837 새로운 게임 2 (파이썬)

https://pacific-ocean.tistory.com/383

[백준] 17837번(python 파이썬)

(내용추가:2022.10.15)

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

N,K=map(int,input().split())
room=[list(map(int,input().split())) for _ in range(N)]
players=[[[]for _ in range(N)] for _ in range(N)]
horse=[[]for _ in range(K+1)]
for t in range(1,K+1):
    x,y,d=map(int,input().split())
    players[x-1][y-1].append(t)
    horse[t]=[x-1,y-1,d-1]

time=0

def red(x,y,nx,ny,num,hd):
    global time
    now=players[x][y].index(num)
    put=players[x][y][now:]
    put.reverse()
    # print(put)
    # print(players[x][y])
    # print(players[nx][ny])
    # print()
    players[nx][ny]+=put
    if put:
        for n in put:

            horse[n][0]=nx
            horse[n][1]=ny
    horse[num]=[nx,ny,hd]
    players[x][y]=players[x][y][:now]
    if len(players[nx][ny])>=4:
        print(time)
        exit()
    # print(players[x][y])
    # print(players[nx][ny])
    # print()


def white(x,y,nx,ny,num,hd):
    global time
    now=players[x][y].index(num)
    put=players[x][y][now:]
    # print(put)
    # print(players[x][y])
    # print(players[nx][ny])
    players[nx][ny]+=put
    if put:
        for n in put:
            horse[n][0]=nx
            horse[n][1]=ny

    players[x][y]=players[x][y][:now]
    horse[num]=[nx,ny,hd]
    if len(players[nx][ny])>=4:
        print(time)
        exit()
    # print(players[x][y])
    # print(players[nx][ny])
    # print()




def blue(x,y,d,num):
    if d==0:
        nd=1
    elif d==1:
        nd=0

    elif d==2:
        nd=3

    elif d==3:
        nd=2

    nx=x+dx[nd]
    ny=y+dy[nd]
    #주의할 포인트!!!
    #파란색이나 범위벗어나면 방향은 바꿔준다!
    #방향 바꿔주고 움직이지는 않게 해둠
    horse[num][2]=nd

    if nx<0 or nx>=N or ny<0 or ny>=N:
        return
    # 흰색을 만났을때
    if room[nx][ny] == 0:

        white(x,y,nx,ny,num,nd)
        return
    # 빨간색을 만났을떄
    elif room[nx][ny] == 1:

        red(x,y,nx,ny,num,nd)
        return
    # 파란색을 만났을 때
    elif room[nx][ny] == 2:
        return

while time<=1000:
    time+=1
    #순서대로 말을 움직인다
    for h in range(1,K+1):
        hx,hy,hd=horse[h]


        nx=hx+dx[hd]
        ny=hy+dy[hd]
        #범위를 벗어났을때
        if nx<0 or nx>=N or ny<0 or ny>=N:
            blue(hx,hy,hd,h)

        #흰색을 만났을때
        elif room[nx][ny]==0:

            white(hx,hy,nx,ny,h,hd)
        #빨간색을 만났을떄
        elif room[nx][ny]==1:

            red(hx,hy,nx,ny,h,hd)
        #파란색을 만났을 때
        elif room[nx][ny]==2:
            blue(hx,hy,hd,h)



print(-1)

좀 더 가독성을 높여서 작성해본 코드.

이 문제는 많은 사람들이

테케 다 맞는데

제출하자마자 틀리는 불상사가 많이 생깁니다.

저도 새로풀 때 그런 일이 생겼습니다.

유사 솔루션과 비교까지 해가면서 체크했는데도

여전히 틀렸다고 뜨길래

입에서 욕이 절로 나왔습니다.

 

틀린 이유는 간단했습니다.

방향을 바꿔주고 움직이든 움지이든 않든

방향 바꾼 건 반영해줘야한다는 것.

문제를 읽어보면

'방향을 바꿔주고 움직이지 않으면 그 자리에 멈춘다'

라고 되어있습니다.

'어처피 방향을 바꾸나 안바꾸나

얘는 다른 칸으로 못가잖아요?'

대략적으로 그린 케이스입니다.

1은 오른쪽을 보고있는데

파란색이니 왼쪽으로 봐야겠죠?

그런데 왼쪽은 범위를 벗어나니 움직이지 않습니다.

이때, 1의 방향을 오른쪽으로 두냐, 왼쪽을 두냐에 따라

그 아래있는 2가 움직일 때

빨간색 격자에 올려지는 경우가 확 달라집니다.

이 경우야 이해를 돕기 위해 간단하게 보여드렸지만

만약 문제가 더 복잡해지면

엄청난 차이를 만들 수 있습니다.