Python [AtoZ] Chapter 04. 구현

[ Table of Contents ]

아이디어를 코드로 바꾸는 구현

1. 피지컬로 승부하기

2. 구현 시 고려해야 할 메모리 제약 사항

3. 채점 환경

4. 구현 문제에 접근하는 방법

5. 예제 : 상하좌우, 시각

 

실전 문제

1. 왕실의 나이트

2. 게임 개발

 

기출 문제

1. 럭키 스트레이트
2. 문자열 재정렬
3. 문자열 압축
4. 자물쇠와 열쇠
5. 뱀
6. 기둥과 보 설치
7. 치킨 배달
8. 외벽 점검

[ Abstract ]

0. 

 

아이디어를 코드로 바꾸는 구현

1. 피지컬로 승부하기

코딩 테스트에서 구현Implementation이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떠 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스크 문제 유형을 포함하는 개념이다. 따라서, 문제 해결 아이디어를 떠올리는 것과 별개로 구현 능력은 코딩 테스트뿐만 아니라 실무에서도 매우 중요하다.

그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않지만, 취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘을 배우기 전에 먼저 다루고자 한다.

흔히 문제 해결 분야에서 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다. 실제 ACM-ICPC, Google Code Jam 등의 대회에 자주 참가하는 사람들이 구현 유형의 문제들을 보면 "알고리즘은 설계했는데, 구현이 먼저 풀 수 있는 문제가 없을 때 푸는 게 좋다"라고 설명하곤 한다.

 

그렇다면 어떤 문제가 구현하기 어려운 문제일까? 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어햐 하는(파싱을 해야 하는) 문제 등이 까다로운 구현 유형의 문제라고 할 수 있다. 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다.

그렇기에 실제로 코딩 테스트에서 구현 문제를 만나면 당황할 수 있다. 어떻게 풀면 될지 대략 감은 오는데, 막상 코드로 옮기려니 무엇부터 작성해야 할지 모를 수 있기 때문이다. 또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 때 불리하다. 이는 언어의 문법을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법이다.

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다루고 있다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 둘 다 구현이 핵심이 되는 경우가 많기 때문에 이 두 유형을 모두 묶어서 구현 장에서 다루고 있다.

코딩 테스트에서는 어떤 환경에서 문제를 풀어야 하는지를 알고 그 환경에 맞게 프로그래밍 언어를 적절히 사용하여 구현하는 일이 중요하므로, 먼저 코딩 테스트 채점 시스템의 제약에 대해 설명한 후 문제를 다루겠다.

 

2. 구현 시 고려해야 할 메모리 제약 사항

C/C++에서 변수의 표현 범위

정수형Integer을 표현할 때는 int 자료형을 주로 사용하며 크기는 4바이트이다. 특히 C/C++, 자바 등을 이용해 코딩할 때는 int 자료형을 필수적으로 이용한다. 보다 큰 수를 처리해야 할 때는 크기가 8바이트인 long long과 같은 자료형을 사용하며, 훨씬 큰 수를 담고 싶을 땐 BigInteger 클래스를 구현하거나 이용해야 한다.

Java의 경우 BigInteger를 표준 라이브러리로 지원하지만, C++의 경우 구글링을 통해 외부 라이브러리 형태 그대로 가져와 사용해야 한다. 하지만, 코딩 테스트 환경에서는 대체로 long long에서 다룰 수 있는 정도로 출제된다.

 

반면에 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다. 실제로 기업 코딩 테스트뿐만 아니라 프로그래밍 대회에 참가할 때에도 파이썬을 선택했다면 정수형 변수의 연산 때문에 머리 아프게 고민해야 할 일은 거의 없을 것이다. 다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자. 

C/C++ 와 Java에서 정수형 종류에 따른 범위
정수형 종류	자료형의 크기	자료형의 범위
int	4 바이트	- 2,147,483,648 ~ 2,147,483,647
long long	8 바이트	- 9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
BigInteger (클래스)	가변적	제한 없음

 

 

파이썬에서 리스트 크기

파이썬에서 여러 개의 변수를 사용할 때는 리스트를 이용하며, 메모리 제한을 고려해야 한다. 대체로 코딩 테스트에서는 128 ~ 512MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다. 이럴 때는 메모리 제한을 염두에 두고 코딩해야 한다.

int 자료형 데이터의 개수에 따른 메모리 사용량
데이터의 개수 (리스트의 길이)	메모리 사용량
1,000	약 4 KB
1,000,000	약 4 MB
10,000,000	약 40 MB

 

파이썬은 다른 언어에 비해서 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자.

일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점 정도만 기억하면 된다. 애초에 대회 문제가 아니라면 복잡한 최적화를 요구하지 않는 것이 일반적이므로 코딩 테스트에서는 이 정도만 기억해도 문제를 푸는 데에 어려움은 없다.

 

3. 채점 환경

실제 온라인 저지 서비스에서 사용되는 채점환경의 시스템 제한은 문제마다, 기관마다 다르다. 파이썬은 C/C++에 비해 동작 속도가 느리다. 그래서 파이썬을 선택했을 때는 C/C++에 비해 2배의 수행 시간 제한을 적용하기도 한다. 파이썬 3.7로 코드를 작성할 때, 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 시간 제한에 안정적이다.

시간 제한이 1초이고, 데이터의 개수(N)가 100만 개인 문제가 있다면 일반적으로 시간 복집도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.

 

4. 구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이지만, 사고력을 요구하는 문제는 나오지 않은 편이라 익숙해지면 오히려 쉽게 풀 수 있다.

실무에서 파이썬으로 프로그램을 개발할 때는 GPU를 연동하며, 반복적인 행렬 계산을 요구하는 복잡한 수학 문제를 풀 때는 C 언어로 작성된 파이썬 코어 소프트웨어가 작동한다. 그렇기 때문에 파이썬을 쓴다고 해서 항상 프로그램의 동작 속도가 느린 것은 아니다. 하지만, 알고리즘 코딩 테스트 환경에서는 GPU 연산을 쓰는 경우가 없기 때문에 그러한 사항을 고려하고 있지 않고 있다.

또한 자동 채점 방식을 이용하는 코딩 테스트 환경에서는 점점 Pypy3를 지원하는 곳이 늘고 있다. 삼성전자 공채가 그러하며, 지원자가 파이썬3로 제출하면 기본으로 Pypy3를 이용해 채점한다. Pypy3는 대략 1초에 2,000만 번에서 1억 번 정도의 연산을 처리할 수 있다.

API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다. 예를 들어 카카오 공채 때 API 개발 문제가 출제된 적이 있는데, 이는 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야 했다. 이는 알고리즘 문제와 별개로 웹 서버나 데이터 분석에 대한 기초 지식도 필요하다.

 

5. 예제

1) 상하좌우

[난이도: 하 / 풀이시간: 15분 / 시간제한: 1초 / 메모리제한: 128MB ]

여행가 A는 NxN크기의 정사각형 공간 위에 서 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)이다.

    L: 왼쪽 / R: 오른쪽 / U: 위로 / D: 아래로 (으로 한 칸 이동)

이때 여행가 A가 NxN크기의 공간을 벗어나는 움직임은 무시된다. 계획서가 주어졌을 때, 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

[입력 조건]

첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1<=N<=100)

둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1<=이동 횟수<=100)

[출력 조건]

첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다.

[입력 예시]

5

R R R U D D

[출력 예시]

3 4

 

[문제 해설]

이 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 예를 들어 이동 횟수가 N번인 경우 시간 복잡도는 O(N)이다. 따라서 이 문제의 시간 복잡도는 매우 넉넉한 편이다.

이러한 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션Simulation 유형으로 분류되며 구현이 중요한 대표적인 문제 유형이다. 다만, 알고리즘 교재나 문제 풀이 사이트에 따라서 다르게 일컬을 수 있으니 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많다는 정도로만 기억하자.

코딩 테스트나 알고리즘 대회에서 가장 난이도가 낮은 1~2번 문제는 대부분 그리디 알고리즘이나 구현 문제이다. 이 두 유형이 논리적 사고력을 확인할 수 있는 가장 기본 난이도의 문제로 적합하기 때문이다. 난이도가 낮은 만큼 합격을 좌우하는 중요한 문제이기도 하다.

#1) 상하좌우
n = int(input()) #NxN행렬 : 5
x,y = 1,1
direc = input().split() #LRUD : R R R U D D

dx = [0,0,-1,1] #LRUD에 따른 이동 방향
dy = [-1,1,0,0]
move = ['L', 'R', 'U', 'D']

for dir in direc: #이동 계획을 하나씩 확인
    for i in range(len(move)): #이동 후 좌표 구하기
        if dir == move[i]:
            nx = x + dx[i] # <------------------ "NxM행렬과 좌표표시와의 관련성", Dive Deep 할 것
            ny = y + dy[i]
    if nx<1 or ny<1 or nx>n or ny>n: #공간을 벗어나는 경우 무시
        continue
    x,y = nx, ny
print(x,y) #3 4

 

 

2) 시각

[난이도: 하 / 풀이시간: 15분 / 시간제한: 2초 / 메모리제한: 128MB ]

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초가지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

    00시 00분 03초

    00시 13분 30초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

    00시 02분 55초

    01시 27분 45초

[입력 조건]

첫째 줄에 정수 N이 입력된다. (0<=N<=23)

[출력 조건]

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

[입력 예시]

5

[출력 예시]

11475

 

[문제 해설]

이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제다. 왜냐하면 하루는 86,400초로, 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지밖에 존재하지 않기 때문이다. 다시 말해 경우의 수가 100,000개도 되지 않으므로 파이썬에서 문자열 연산을 이용해 3이 시각에 포함되어 있는지 확인해도 시간 제한 2초 안에 문제를 해결할 수 있다.

따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인하면 될 것이다. 전체 시, 분, 초에 대한 경우의 수는 24 x 60 x 60이며 3중 반복문을 이용해 계산할 수 있다.

이러한 유형은 완전 탐색Brute Forcing 유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 완전 탐색 문제 또한 구현이 가장 중요한 대표적인 문제 유형인데, 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.

다음 소스코드에서는 매 시각을 문자열로 바꾼 다음 문자열에 '3'이 포함됐는지 검사한다. 다시 말해 00시 00분 00초부터 23시 59분 59초까지 1초씩 늘리며 시, 분, 초를 문자열 자료형으로 변환하여 합친다. 예를 들어 03시 20분 35초일 때를 확인한다면, 이를 '032035'로 만들어서 '3'이 '03035'에 포함되어 있는지를 체크하는 방식을 이용한다.

#2) 시각
n = int(input()) #5

cnt = 0
for i in range(n+1): #시
    for j in range(60): #분
        for k in range(60): #초
            #매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k): # <------ int to string 방법
                cnt += 1
print(cnt) #11475

 

 

실전 문제

1. 왕실의 나이트

[난이도: 하 / 풀이시간: 20분 / 시간제한: 1초 / 메모리제한: 128MB]

행복 왕국의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 칸에 나이트가 서 있다. 나이트는 매우 충서스러운 신하로서 매일 무술을 연마한다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

    1. 수평으로 두 칸 이동한 뒤 수직으로 한 칸 이동하기

    2. 수직으로 두 칸 이동한 뒤 수평으로 한 칸 이동하기

이처럼 8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.

예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 다음 2가지이다.  정원 밖으로 나갈 수 없기 때문이다.

    1. 오른쪽으로 두 칸 이동 후 아래로 한 칸 이동하기(c2)

    2. 아래로 두 칸 이동 후 오른쪽으로 한 칸 이동하기(b3)

또 다른 예로 나이트가 c2에 위치해 있다면 나이트가 이동할 수 있는 경우의 수는 6가지이다. 이건 직접 계산해보시오.

[입력 조건]

첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a2처럼 열과 행으로 이뤄진다.

[출력 조건]

첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

[입력 예시]

a1

[출력 예시]

2

 

[문제 해설]

왕실의 나이트 문제는 앞서 다루었던 예제 4-1 상하좌우 문제와 유사하다. 나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동하면 된다. 다만, 8 x 8 좌표 평면을 벗어나지 않도록 꼼꼼하게 검사하는 과정이 필요하다.

나이트의 경로를 steps 변수에 넣는다면, 이 2가지 규칙에 따라 steps = [(-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1)]로 값을 대입할 수 있다. 현재 위치를 기준으로 아래쪽과 오른쪽은 양수의 값을, 위쪽과 왼쪽은 음수의 값을 대입한 결과이다. 이제 나이트의 현재 위치가 주어지면 현재 위치에서 이동 경로를 더한 다음, 8 x 8 좌표 평면에 있는지 확인하면 된다. 이 과정은 반복문으로 처리할 수 있다.

 

조금 더 까다롭게 문제를 출제한다면 입력 문자가 열과 행이 아닌 1a와 같은 행과 열 형태로 들어왔을 때의 예외 처리를 요구할 수도 있다. 이런 다양한 구현 유형에 대비하기 위해서 파이썬 문법을 자유롭게 사용할 수 있도록 훈련하는 것이 중요하다.

다음 답안 예시에서는 나이트가 이동할 수 있는 경로를 steps 변수에 하나씩 담은 것을 확인할 수 있다. 이러한 8가지 경우의 수를 반복문을 이용하여 하나씩 검사한다.

 

상하좌우 문제에서는 dx, dy 리스트를 선언하여 이동할 방향을 기록할 수 있도록 하였다. 이번 소스코드에서는 steps 변수가 dx와 dy 변수의 기능을 대신하여 수행한다. 2가지 형태 모두 자주 사용되므로, 참고하도록 하자.

#1. 왕실의 나이트
'''
ord(문자) => Unicode로 반환 -----------> ex) ord('a') = 97
'''
#현재 나이트의 위치 입력받기
loca = input() #a1
row = int(loca[1]) #행 = loca[1]
column = int(ord(loca[0])) - int(ord('a')) + 1 #열 = loca[0]

#나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2,-1), (-1,-2), (1,-2), (2,-1),
         (2,1), (1,2), (-1,2), (-2,1)] #steps = (행,열)

#8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    #이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    #해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1
print(result) #2

2. 게임 개발

[난이도: 중 / 풀이시간: 40분 / 시간제한: 1초 / 메모리제한: 128MB]

현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x N 크기의 직사각형으로, 각각은 칸의 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.

맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.

    1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.

    2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

    3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 매뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

[입력 조건]

1. 첫째 줄에 맵의 세로 크기 N과 가로크기 M을 공백으로 구분하여 입력한다. (3<= N, M <= 50)

2. 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백을 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다. (0: 북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽)

3. 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어 있다. (0: 육지, 1: 바다)

4. 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

[출력 조건]

첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

[입력 예시]

4 4       #4x4맵 생성

1 1 0    #(1,1)에 북쪽(0)을 바라보고 서 있는 캐릭터

1 1 1 1 #첫 줄은 모두 바다

1 0 0 1 #둘째 줄은 바다/육지/육지/바다

1 1 0 1 #셋째 줄은 바다/바다/육지/바다

1 1 1 1 #넷째 줄은 모두 바다

[출력 예시]

3

 

[문제 해설]

전형적인 시뮬레이션 문제이다. 삼정전자 공채 코딩 테스트에서 자주 출제되는 대표적인 유형이기도 하다. 별도의 알고리즘이 필요하기보다는 문제에서 요구하는 내용을 오류 없이 성실하게 구현만 할 수 있다면 풀 수 있다는 특징이 있다.

다만, 문제가 길고 문제를 바르게 이해하여 소스코드로 옮기는 과정이 간단하지 않다. 따라서 이러한 문제를 잘 풀 수 있도록 반복적인 숙달이 필요하다.

문제 풀이를 위한 중요한 테크닉을 다시 설명하자면, 일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다. 예를 들어 다음의 답안 예시 코드에서는 현재 캐릭터가 북쪽을 바라보고 있을 때는 북쪽으로 이동하기 위해 x와 y좌표를 각각 dx[0], dy[0]만큼 더한다. 다시 말해 현재 위치에서 (-1, 0)만큼 이동시키는 것이다. 이처럼 코드를 작성하면, 반복문을 이용하여 모든 방향을 차례대로 확인할 수 있다는 점에서 유용하다.

그리고 답안 예시 코드에서는 리스트 컴프리헨션 문법을 사용해 2차원 리스트를 초기화했다. 파이썬에서 2차원 리스트를 선언할 때는 컴프리헨션을 이용하는 것이 효율적이라는 점을 기억하자.

왼쪽으로 회전하는 함수 turn_left( )에서 global 키워드를 사용했는데, 이는 정수형 변수인 direction 변수가 함수 바깥에서 선언된 전역변수이기 때문이다.

#2. 게임 개발
n, m = map(int, input().split()) #NxM, 4 4

#방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]

#현재 캐릭터의 x좌표, y좌표, 방향을 입력받기
x, y, direction = map(int, input().split()) #1 1 0, direction은 바라보는 방향 (0북 1동 2남 3서)
d[x][y] = 1 #현재 좌표 방문처리

#전체 맵 정보 입력받기
arr = []
for i in range(n):
    arr.append(list(map(int, input().split()))) #1 1 1 1, 1 0 0 1, 1 1 0 1, 1 1 1 1

#북,동,남,서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

#왼쪽으로 회전
def turn_left():
    global direction
    direction -= 1 #왼쪽으로 회전
    if direction == -1: #북쪽에서 회전하면 서쪽 : -1 -> 3
        direction = 3 # <--------------- ????????

#시뮬레이션 시작
cnt = 1
turn_time = 0
while True:
    #왼쪽으로 회전
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]

    #회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if d[nx][ny] == 0 and arr[nx][ny] == 0: #d 방문위치, arr 바다위치
        d[nx][ny] = 1
        x = nx
        y = ny
        cnt += 1
        turn_time = 0
        continue
    
    #회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
        turn_time += 1 #한번 더 회전

    #네 방향 모두 갈 수 없는 경우
    if turn_time == 4: #3의 경우 : 바라보는 방향 유지하며, 한 칸 뒤로
        nx = x - dx[direction]
        ny = y - dy[direction]

        #뒤로 갈 수 있다면 이동하기
        if arr[nx][ny] == 0:
            x = nx
            y = ny

        #뒤가 바다로 막혀있는 경우
        else:
            break #빠져나감
        turn_time = 0 #다시 1의 경우로 돌아감
#정답 출력
print(cnt) #3

 

 

기출 문제

1. 럭키 스트레이트
2. 문자열 재정렬
3. 문자열 압축
4. 자물쇠와 열쇠
5. 뱀
6. 기둥과 보 설치
7. 치킨 배달
8. 외벽 점검

 

 

이 글은 주인장의 자습 목적을 위해 <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 99.99% 참고하여 만들었다.