삼성 SW 역량 테스트 : 새로운 게임 2 (백준 17837번)

해당 문제는 백준에서 제공된 기출 문제입니다.

[문제 설명 및 파악]

백준 17837번: 새로운 게임 2

17837번: 새로운 게임 2

이 문제도 어떤 것을 요구하는지, 그 요구사항을 어떻게 풀어나가야 할지 코딩을 구현하기 전에 생각해보자. 먼저 이 문제가 요구하는 것은 정해진 맵에서 말들이 위치와 방향이 주어졌을 때 해당 조건들을 만족하며 맵의 한 칸에 말이 4개 이상 있을 수 있는지 파악하는 것이다. 그렇다면 이 문제는 어떻게 접근해야 할까? 주어진 조건들을 보면 말들의 위치가 같아지면 쌓인다라는 것을 알 수 있다. 이 힌트를 통해서 우린 스택으로 접근해야 된다라는 것을 알 수 있다. 그렇다면 스택은 어떤 식으로 구현해야 할까? 스택 하나를 따로 만들어서 말들이 쌓일 때마다 저장하고 움직일 때 마다 빼주고 하기엔 너무나 다양한 경우의 수와 위치가 있다. 그래서 우린 이 스택 자체를 맵으로써 표현해야 된다는 것을 파악해야 된다. (이걸 생각해내냐 못하냐가 이 문제의 핵심인 것 같다). 맵의 모든 칸마다 스택 자체를 넣어주고, 말들이 이동할 때마다 빼주고 넣어주고 해주면 더 쉽게 위치를 파악하며 접근할 수 있다. 그럼 이를 바탕으로 코드를 구현해 보자.

---

[문제풀이]

# 동 서 북 남
# →, ←, ↑, ↓
dy = [0, 0, -1, 1]
dx = [1, -1, 0, 0]

def new_direction(d):  # 방향을 반대로 변환
    if d % 2 == 0:
        return d + 1
    else:
        return d - 1

def game(k, game_map, horses_loc_dir):
    N = len(game_map)
    loc_map = [[[] for _ in range(N)] for _ in range(N)] #(핵심!) 현재 맵의 모든 칸마다 stack을 생성해줌
    idx = 1 #말의 번호
    for y, x, d in horses_loc_dir:
        loc_map[y][x].append(idx) # 스택맵에다 해당 말의 현재 위치를 표시
        idx+=1 #다음 말로
    turn = 1 # 턴

    while turn <=1000: # 턴이 1000을 넘을경우 종료
        # 한턴에 각각의 말의 방향에 따라 이동시키기위한 반복문
        for horse in range(k):
            cur_y,cur_x,d = horses_loc_dir[horse] #현재 말의 위치와 방향
            # print('{},{}'.format(horse+1, d)) #현재 말의 위치와 방향 확인
            next_y = cur_y+dy[d] # 이동할 칸_row
            next_x = cur_x+dx[d] # 이동할 칸_column
            # 다음 이동하고자 하는 칸이 벽이나 파란칸일 경우 (첫번째)
            if not 0 <= next_y < N or not 0 <= next_x < N or game_map[next_y][next_x] == 2:
                d = new_direction(d) # 방향 반대로 변환
                horses_loc_dir[horse][2] = d # 바뀐 방향 반영
                next_y = cur_y + dy[d] # 이동할 칸_row -> 바뀐 방향에 따라 새로 설정
                next_x = cur_x + dx[d] # 이동할 칸_col -> 바뀐 방향에 따라 새로 설정

            # 파란색일 경우 이미 방향을 반대로 변경된 상태에서 마주함 (방향을 반대로 변경된 이후의 시점)
            # or 파란색이 아니면 그냥 처음 시작되는 조건문 이라고 생각 (어떠한 이동없이 처음 마주치는 조건)

            # 그때 다음 이동할 칸이 파란색이거나 벽일 경우
            if not 0 <= next_y < N or not 0 <= next_x < N or game_map[next_y][next_x] == 2:
                continue # 아무 것도 하지 않음

            # 그게 아닌 다음 이동할 칸이 흰색칸인 경우 (앞으로 이동)
            elif game_map[next_y][next_x] == 0:
                idx = loc_map[cur_y][cur_x].index(horse+1) # 해당 말의 상태 확인(혼자인가 아니면 다른말과 같이 있나)
                to_move = loc_map[cur_y][cur_x][idx:] # 자신의 위로 쌓인 말들과 함께 이동 (쌓인 말이 없으면 자신만 이동)
                loc_map[next_y][next_x].extend(to_move) # 이동할 칸에 해당 말 혹은 말들을 추가(스택처럼 쌓아줌)
                for h in loc_map[cur_y][cur_x][idx:]: # 이동된 말들의 위치 변경
                    horses_loc_dir[h-1] = [next_y,next_x,horses_loc_dir[h-1][2]] # 방향은 그대로 저장
                del loc_map[cur_y][cur_x][idx:] # 이동된 말들의 이전 위치 제거

            # 그게 아닌 다음 이동할 칸이 빨간색칸인 경우 (앞으로 이동하며 쌓여져 있는 순서 변경)
            # 다음 칸으로 말들을 이동시킬 때 순서를 반대로 저장하는 것 제외하고는 흰색과 동일
            elif game_map[next_y][next_x] == 1:
                idx = loc_map[cur_y][cur_x].index(horse + 1)
                to_move = loc_map[cur_y][cur_x][idx:]
                loc_map[next_y][next_x].extend(reversed(to_move)) # 이동할 칸에 해당 말 혹은 말들을 반대의 순서로 추가(흰색칸과의 차이)
                for h in loc_map[cur_y][cur_x][idx:]: #
                    horses_loc_dir[h - 1] = [next_y, next_x, d]
                del loc_map[cur_y][cur_x][idx:]

            # 이동한 칸에서 말이 4개 이상있을 경우 종료
            if len(loc_map[next_y][next_x]) >= 4:
                return turn

        turn += 1 #다음 턴
        
    return -1 # while문 도중에 return 되지 않았다면 -1 반환

앞서 말했듯이 스택자체를 맵으로써 표현한다는 것도 핵심이지만, 파란색 칸을 만날 경우, 흰색칸을 만날경우, 빨간 칸을 만날 경우의 조건문의 순서를 어떻게 표현해내냐도 핵심이다. 파란 칸이나 벽을 만날 경우일 때는 방향을 반대로 변경해주고 한번 더 이동 하기에 파란칸이나 벽을 만날 경우를 미리 처리해서 그 만난 후를 기준으로 다시 흰, 빨, 파를 만날 경우로 처리해야 된다. 그리고 빨간색 칸의 경우 말이 쌓인 순서를 반대로 바꾸어주고 append하는 것만을 주의하면 이 문제는 어렵지 않게 풀 수 있다.

---

[잘못된 풀이]

내가 처음 이 문제를 접했을 때는 스택을 이용해서 풀어야 된다는 생각을 했지만, 스택 하나만을 가지고 처리하려고 했던 점이 실수였던 것 같다. 즉, 맵의 모든 칸을 스택으로 표현할 생각을 못했다. 이러한 문제는 정말 문제에 대한 경험을 늘려가면서 고쳐야 할 부분인 것 같다. 또한, 조건문의 순서를 복잡하게 표현하여 쓸데없는 코드가 생기기도 했다.

---

[마무리]

삼성 기출은 항상 어렵게 느껴지는 것 같다. 단순히 생각해서 풀리는 것이 아닌, 여러 가지를 모두 고려해야지만 풀리는 문제들이 꽤 많은 것 같다. 특히나 이러한 문제들에 나는 약한 것 같다. 실전에서 빠르고 정확하게 문제를 파악하고 구현하려면 맵이나 그래프 유형의 문제를 많이 풀어보고 실력을 늘려야 한다고 생각한다.