[알고리즘] 0409 회고 노트 - 삼성 SW역량테스트 "뱀" 문제

 

 

 

오늘은 삼성 역량SW테스트의 뱀 문제를 풀었다.

www.acmicpc.net/problem/3190

 

해당 문제는 2차원 배열의 특정 위치에서 동, 남, 서, 북의 위치로 이동하는 기능을 구현해야 한다. 또한 매 시점마다 뱀이 존재하는 위치를 항상 2차원 리스트에 기록해야 한다.

 

이러한 시뮬레이션 문제 유형은 문제에서 주어진 TC를 직접 그려보는 것이 이해하는 데 좋다.

 

 

풀이 시간은 40분으로 예전에 뱀 게임을 MFC로 경험해본 적이 있어서인지 문제 이해 자체는 수월했다.

이번 문제를 통해 새로 알게된 점을 정리해보았다.

 

 

 

파이썬 2차원 리스트 선언

 

예를 들어 전부 0으로 초기화된 N x N 리스트를 만들고자 한다. 기존에 내가 만들던 방식은 다음과 같았다.

 

<기존>

data = []
for i in range(n):
	temp = []
    for j in range(n):
    	temp.append(0)
    data.append(temp)

틀린 방법은 아니지만, 개인적으로 풀이에 나온 방식이 더 간편해 보인다.

 

<풀이>

책에서는 N x N 의 정보를 담는 2차원 리스트를 생성할 때 (N+1) x (N+1) 크기로 선언을 하였다. 이렇게 하는 이유가 있었던 거 같은데 지금 찾으려 하니 안 보인다. 알고리즘 책을 2회독할 때 찾아내면 추가해야 겠다.

data =[[0] *(n+1) for _ in range(n+1)]

 

 

파이썬 입력 방식

 

공백으로 띄어져 있는 2개의 숫자를 입력받을 땐 버릇 처럼 아래 코드를 작성하였다. 

a, b = map(int, input().split())

그러다 갑자기 공백으로 분리된 2개의 문자라던가, 하나는 숫자, 다른 하나는 문자일 때 순간 당황하곤 한다. 그럴땐 그냥 str형으로 전부 입력받아서 숫자만 나중에 int형으로 형변환해주면 된다.

# 두개가 다 문자/ 하나는 숫자, 하나는 문자일 경우
a, b = input().split()

# a, b = map(str, input().split())도 가능하긴 하나 위에 코드가 더 짧다.

 

이전의 값을 저장해야 할 필요가 있는 변수 다루는 방식

코드를 작성하다 보면, 반복문을 돌면서 이전의 값을 불러와 비교하거나 사용해야 하는 경우가 있다. 

아무래도 나는 파이썬보다 C, C++을 다룬 경험이 많다 보니 다음과 같이 코드를 작성하는 것이 버릇처럼 들었다.

 

<기존>

prev = 0 # 이전 값 초기화
 
for i in range(1, n):
  cur = i # 현재값 갱신
  prev = cur # 이전값 갱신

위 방식이 틀렸다는 것은 아닌데 개인적으로 해당 방식을 구현 문제에 적용하려고 하면, 다른 조건들까지 한꺼번에 생각해야 되서 여러모로 헷갈린다. (나만 그런 거일수도 있다) 실제로 prev, cur 변수를 선언하기 시작하면 벌써부터 스트레스를 받으며 집중력이 떨어지곤 했다.

 

근데 책의 풀이에선 queue를 이용해서 쉽게 다루는 것을 볼 수 있었다. 

 

<풀이>

q = []

for i in range(1,n):
	q.append(i) # 현재 값 queue에 갱신
    q.pop(0) # 이전 값 얻어오기

 

나는 이 방식이 더욱 쉽게 다가왔다. 물론 queue를 다루는게 아직 낯설긴 하지만, prev와 cur로 고생하는 것보단 queue에 익숙해지도록 여러번 써보는게 좋을것 같다!

 

 

동서남북으로 이동하는 문제

이번에 푼 "뱀" 문제는 뱀이 상하좌우로 이동을 할 수 있는 문제였다. 해당 책에서는 이전에 상하좌우로 움직이는 일이 있을 경우 다음과 같이 상하좌우에 따른 x, y값의 변화를 미리 선언해놓으면 좋다고 하였다.

 

<풀이>

# 동, 남, 서, 북 
dx = [0, 1, 0,-1]
dy = [1, 0, -1, 0]

 

우리가 일반적으로 동서남북이라고 말하는 것에 반해 동, 남, 서, 북 순으로 x, y값 변화를 써놓은 이유는 해당 뱀 문제에서 뱀이 방향을 틀 때 90도로밖에 못 틀기 때문이다.

 

동, 남, 서, 북을 각각 0, 1, 2, 3이라는 숫자로 설정한다. dx, dy의 index값이기도 하다. 문제에선 뱀이 처음에 동쪽을 바라보고 있다 했기 때문에 방향을 나타내는 변수 direction을 0으로 초기화 한다.

 

뱀이 동->남쪽(왼쪽으로 90도)으로 회전하고 싶으면 direction 변수를 +1 더하면 된다.

뱀이 동->북쪽(오른쪽으로 90도)으로 회전하고 싶으면 direction 변수를 -1하면 된다.

 

위의 경우는 단순히 +1, -1 연산을 해도 되지만, 다음과 같은 경우엔 문제가 발생한다.

뱀이 북->동쪽(왼쪽으로 90도)으로 회전하고 싶을 때 단순히 direction += 1 연산을 하면 direction 값이 5가 되버려서 index가 out of range가 되버린다.

 

그러므로 이를 해결하기 위해 direction + 1 값에 %4 연산을 해줘야 한다. 즉 direction = (direction + 1) % 4를 해주면 정상적으로 동쪽을 뜻하는 1 값이 direction에 저장된다.

 

마찬가지로 뱀이 오른쪽으로 90도 회전하고 싶을 땐 direction = (direction -1) % 4를 해주면 정상적으로 오른쪽으로 90도를 회전하게 된다. 

 

def turn(direction, c): # direction: 방향을 저장 c: 왼쪽으로 회전(L), 오른쪽으로 회전인지(D)
	if c == "L":
    	direction = (direction - 1) % 4
    else:
    	direction = (direction + 1) % 4
    return direction

---

알고리즘 회고 끝!

 

매번 문제만 주구장창 풀다가 이번에 처음으로 써보는데 생각보다 괜찮은 거 같다.

문제만 풀 땐, 시간 재고 문제 푼 다음에 시간 안에 다 못 풀면 답 보면서 스르륵 훑어보며 아~ 그랬구나. 음 그렇군 이러면서 이해하고 코드를 따라 쓰는데에만 급급했다.

 

물론 그렇게 해서 바로 내 것으로 만들었으면 상관이 없는데 뭔가 그렇게 하면 전체의 30퍼정도밖에 이해하지 못하는 느낌이었다. 또한 다음에 그것과 비슷한 문제를 풀 때 똑같은 이유로 못 풀 것 같은 불길함이 들어 이제부턴 시간이 좀 걸리더라도 이렇게 회고 노트를 쓰는게 좋을거 같다.

 

사실 말이 회고노트이지 그냥 오답 노트나 다름 없다 ㅋㅋㅋ