Problem

특정 방향으로 n번 이동할 때, 해당 칸이 특정 조건을 만족하는지 확인한다.

Submitted Code

Python

 1 def do_game(maps, r, c):
 2     N = len(maps)
 3     y, x = r - 1, c - 1
 4     dirs = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}
 5	
 6     path = [[1] * N for _ in range(N)]
 7	
 8     step = 0
 9     stack = []
10     while path[y][x]:
11         step += 1
12         path[y][x] = 0
13 
14         if not stack:
15             cnt, cmd = maps[y][x]
16             for _ in range(cnt):
17                 stack.append(dirs[cmd])
18
19         dy, dx = stack.pop()
20         ny, nx = y + dy, x + dx
21         y = (ny % N) if ny >= 0 else N - 1
22         x = (nx % N) if nx >= 0 else N - 1
23
24     return step
25
26 N = int(input())
27 rg, cg = map(int, input().split())
28 rp, cp = map(int, input().split())
29 maps = []
30 for _ in range(N):
31     maps.append([(int(i[:-1]), i[-1]) for i in input().split()])
32
33 scores = {"goorm": do_game(maps, rg, cg), 
34           "player": do_game(maps, rp, cp)}
35 msg = f"goorm {scores['goorm']}" if scores['goorm'] > scores['player']\
36         else f"player {scores['player']}"
37 print(msg)

Line 1-24

do_game 함수는 지시 사항이 기록된 2차원 리스트 maps, 말의 위치 r, c를 입력하면, 말이 게임 종료 전까지 방문한 칸의 개수를 반환한다.

Line 2

격자 보드의 크기를 N에 대입한다.

Line 3

말의 위치 r과 c의 범위가 1 ~ N이므로, 그대로 리스트 인덱스로 사용하면 IndexError가 발생한다. 1 ~ N을 리스트의 인덱스 범위인 0 ~ N-1로 변경하여 y와 x에 대입한다.

• 2차원 리스트에 padding을 넣어서 말의 위치 범위와 리스트의 인덱스 범위를 같게 만들 수도 있다. 하지만, 이번 문제에서는 범위를 벗어나는 경우를 판단하는 게 중요하기 때문에 격자 크기와 같도록 2차원 리스트를 만들어서 혼란의 여지를 줄이고자 하였다.

Line 4

<cmd>에 따라 이동 방향을 설정한다.

Line 6

maps와 동일한 크기로 2차원 리스트를 생성하고, 1로 초기화한다.

• Line 10에서 maps의 값으로 while문을 실행하도록 작성했기 때문에, == 연산자 없이 사용할 수 있도록 1로 초기화했다.
• True로 초기화할 수도 있지만, paths의 True 값이 '방문한 칸'으로 해석될 수도 있어서 숫자 1로 설정했다.

Line 8

step 변수에 시작 칸을 포함한 방문 칸의 개수를 기록한다.

Line 9

stack에 <cnt> 개수만큼 이동 방향 dirs의 value을 추가한다.

• stack에 지시 시항을 바로 추가할 수도 있다.

  • 하지만, 이동 중에 이미 방문한 칸이 나오면 <cnt>를 다 채우지 않더라도 종료해야 하기 때문에, 이동을 칸마다 분리했다.

• 다른 방법으로, stack에 지시 시항을 추가하고 while문 내부에 지시 사항의 <cnt>만큼 이동을 수행하는 for문을 넣을 수도 있다.

  • 하지만, 이 경우에 게임 종료 구문이 while문 실행 조건과 for문 내부의 if문-break로 두 군데가 생기기 때문에 좋지 않은 코드라고 판단했다.

Line 10-12

(y, x)가 방문하지 않은 칸인 경우(path[y][x] == 1), 게임을 진행한다. 해당 (y, x) 칸은 방문으로 표시(path[y][x] = 0)하고, 방문 칸의 개수(step)을 1만큼 증가시킨다.

Line 14-17

이전 도착 칸의 지시 사항을 모두 이행하면 stack이 비어 있는 상태가 된다. stack이 비었으면, (y, x) 칸의 지시 사항에 따라 이동할 방향을 <cnt> 개수만큼 stack에 추가한다.

Line 19-20

stack에서 이동 방향을 받고, 다음 이동 칸 (ny, nx)를 계산한다.

• deque를 사용해서 첫 번째 값을 받을 수도 있다.
  • 하지만, stack에 값이 있을 때는 항상 동일한 방향만 포함되어 있기 때문에 마지막 값부터 받아도 된다.

Line 21-22

다음 이동 칸 (ny, nx)이 격자 크기 N을 넘어가면

1. N보다 큰 값으로 넘어갈 때
   한 칸씩 이동하기 때문에 N보다 큰 값은 좌표값이 N이 되는 경우이다. 좌표값을 N으로 나눈 나머지를 받으면 0이 된다.

2. N보다 작은 값으로 넘어갈 때
   마찬가지 이유로 좌표값이 -1이 되는 경우이다. 좌표값이 음수일 때 N - 1로 이동시킨다.

Line 24

while문 종료 후 방문 칸의 개수 step을 반환한다.

Line 26-28

문제의 입력값을 변수에 대입한다.

Line 29-31

지시 사항을 기록할 2차원 리스트 maps를 만들고, '1L'과 같이 숫자+알파벳 형태인 지시 사항을 (1, 'L') 형태로 리스트에 저장한다.

Line 33-34

goorm과 player의 점수를 계산한다.

Line 35-37

승자에 따라 출력 메시지를 결정하고, 이를 출력한다.

C++

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
int step(int r, int c, string maps[200][200], int N);

int main() {
	int N, Rg, Cg, Rp, Cp;
	cin >> N >> Rg >> Cg >> Rp >> Cp;
	
	string maps[200][200] = {};
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> maps[i][j];
		}
	}
	
	int goorm = step(Rg, Cg, maps, N);
	int player = step(Rp, Cp, maps, N);
	
	string msg = (goorm > player)? "goorm " + to_string(goorm): "player " + to_string(player);
	cout << msg;
	
	return 0;
}

int step(int r, int c, string maps[200][200], int N) {
	int cnt_step = 0;
	int y = r - 1, x = c - 1;
	int visited[200][200] = {0};
	map<char, pair<int, int>> dirs = {
		{'L', make_pair(0, -1)},
		{'R', make_pair(0, 1)},
		{'U', make_pair(-1, 0)},
		{'D', make_pair(1, 0)}
	};
	
	string script = maps[y][x];
	while (visited[y][x] == 0) {
		visited[y][x] = 1;
		cnt_step++;		
		int cnt = stoi(script.substr(0, script.length() - 1)) - 1;
		char cmd = script[script.length() - 1];
		int ny = (y + dirs[cmd].first) % N;
		int nx = (x + dirs[cmd].second) % N;
		y = (ny >= 0)? ny: N + ny;		
		x = (nx >= 0)? nx: N + nx;
		
		if (cnt == 0){
			script = maps[y][x];
		} else {
			script.replace(0, script.length() - 1, to_string(cnt));
		}
	}
		
	return cnt_step;
}

Challenge Review

QnA로 문제 출제자와 소통할 수 있었다.