[알고리즘] Implementation (구현) - (2)

🔒 문제1 : 왕실의 나이트

행복 왕국의 왕실 정원은 체스판과 같은 8x8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다.

나이트는 말을 타고 있기 때문에 이동을 할 때는 1자 형태로만 이동할 수 있으며, 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

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

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

예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 다음 2가지이다. a1의 위치는 좌표 평면에서 구석의 위치에 해당하며 나이트는 정원의 밖으로는 나갈 수 없기 때문이다.

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

또 다른 예로 나이트가 c2에 위치해 있다면 나이트가 이동할 수 있는 경우의 수는 6가지이다.

1. 왼쪽 수평으로 두 번 이동 후 위쪽으로 한 번 이동 : a1
2. 왼쪽 수평으로 두 번 이동 후 아래쪽으로 한 번 이동 : a3
3. 아래쪽으로 두 번 이동 후 왼쪽 수평으로 한 번 이동 : b4
4. 아래쪽으로 두 번 이동 후 오른쪽 수평으로 한 번 이동 : d4
5. 오른쪽 수평으로 두 번 이동 후 위쪽으로 한 번 이동 : e1
6. 오른쪽 수평으로 두 번 이동 후 아래쪽으로 한 번 이동 : e3

위쪽으로 두번 이동하는 경우는 시작 위치가 c2이기 때문에, 정원을 벗어나게되서 고려하지 않는다.

⌨ 입력

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

🖨 출력

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

📚 예제

Ex)

- 입력 예시

a1

- 출력 예시

2

📌 풀이

나이트는 두 가지 경로로 움직일 수 있다고 했다.

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

그런데 위의 경로를 조금 더 풀어 쓰면, 수평은 왼쪽, 오른쪽 총 2가지가 있고, 수직의 경우도 위, 아래 2가지가 있다.

그래서 저 두 가지 경로는 사실상 총 8가지로 나눌 수 있다.
(위 * 2 , 오른쪽 * 1), (위 * 2 , 왼쪽 * 1), (오른쪽 * 2 , 위 * 1), (오른쪽 * 2 , 아래 * 1), (아래 * 2 , 오른쪽 * 1), (아래 * 2 , 왼쪽 * 1), (왼쪽 * 2 , 위 * 1), (왼쪽 * 2 , 아래 * 1)

위,아래로 이동하는 것은 행이 이동하는 것이고, 오른쪽, 왼쪽으로 이동하는 것은 열이 이동하는 것이다.

따라서 steps = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (2, 1), (2, -1), (1, -2), (1, 2)] 로 값을 대입하여 풀 수 있다.

이제 현재 위치를 받아와서 위의 steps를 for문을 이용해서 처리하면서, 정원밖으로 나가는 경우를 제외하고 가능한 이동 위치를 세면 된다.

이 문제는 입력값이 문자열로 들어오기 때문에 문자를 아스키코드로 변경하기 위해 ord(문자[0]) - 97를 썼고, 뒤의 숫자는 문자[1] - 1을 사용해서 각각 행과 열의 인덱스 번호로 쓸 수 있게 했다.

🔑 python 코드

• 내 코드

#왕실의 나이트
import sys
input = sys.stdin.readline
temp = list(input())
coor = [int(temp[1]) - 1,ord(temp[0]) - 97] # 문자를 아스키코드로 바꾸기 위해 ord 사용
ans = 0

#위로 두 칸
if(coor[0] - 2 >= 0):
    if(coor[1] - 1 >= 0):
        ans += 1
    if(coor[1] + 1 < 8):
        ans += 1
#아래로 두 칸
if(coor[0] + 2 < 8):
    if(coor[1] - 1 >= 0):
        ans += 1
    if(coor[1] + 1 < 8):
        ans += 1
#왼쪽으로 두 칸
if(coor[1] - 2 >= 0):
    if(coor[0] - 1 >= 0):
        ans += 1
    if(coor[0] + 1 < 8):
        ans += 1
#오른쪽으로 두 칸
if(coor[1] + 2 < 8):
    if(coor[0] - 1 >= 0):
        ans += 1
    if(coor[0] + 1 < 8):
        ans += 1

print(ans)

• 정답 코드

# 현재 나이트의 위치 입력받기

input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

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

#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 : 게임 개발

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

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

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향 (반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

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

⌨ 입력

• 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3 <= N, M <= 50)
• 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.
  • 0 : 북쪽
  • 1 : 동쪽
  • 2 : 남쪽
  • 3 : 서쪽
• 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어 있다.
  • 0 : 육지
  • 1 : 바다
• 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

🖨 출력

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

📚 예제

Ex)

- 입력 예시

4 4       # 4 x 4 맵 생성
1 1 0     # (1, 1)에 북쪽 (0)을 바라보고 서 있는 캐릭터
1 1 1 1   # 첫 줄은 모두 바다
1 0 0 1   # 둘째 줄은 바다/육지/육지/바다
1 1 0 1   # 셋째 줄은 바다/바다/육지/바다
1 1 1 1   # 넷째 줄은 모두 바다

- 출력 예시

3

📌 풀이

이런 좌표 문제가 가장 헷갈리는 이유는 개인적으로는 좌표에 행렬을 대입할때, 가로 세로 좌표를 적는 방식과 행렬이 반대이기 때문이다.

그냥 1차원적으로 생각해서 행렬을 좌표에 대입하면, (x,y)좌표를 반대로 생각하는게 헷갈렸었다.

그래서 그냥 축을 왼쪽으로 90도 회전시켜서 생각해보기로 했다.

위 그림을 보면 동서남북을 나타내는 방위가 눕혀져있는 것을 볼 수 있다.

그래서 북쪽으로 가기 위해서는 x축 방향으로 -1 만큼, 동쪽으로 가기 위해서는 y축 방향으로 1만큼 이동한다.

이것을 식으로 나타내면

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

로 나타낼 수 있다.

문제에서 주어진 내용으로는 북, 동, 남, 서 순으로 0, 1, 2, 3이다.

왼쪽으로 회전해보면 아래 그림처럼 북 -> 서 -> 남 -> 동 -> 북 ... 순이고 숫자로는 0 -> 3 -> 2 -> 1 순이다.

그래서 왼쪽으로 회전한 방향의 수는 이전 방향에 + 3을 해준 값을 4로 나눈 나머지와 같다.

쉽게 말해보자면, next_dir = (cur_dir + 3) % 4이다.

이것들을 기억하고 문제에서 말하는대로 코드를 짜주면 된다.

🔑 python 코드

# 게임 개발

import sys
input = sys.stdin.readline

# N(세로-행), M(가로-열) 입력 받기
N, M = map(int, input().split())

# 캐릭터 현재 위치 및 방향 입력 받기
x, y, dir = map(int, input().split())

# 지도 입력 받기
Map = [list(map(int, input().split())) for _ in range(N)]

# 방문한 위치 확인 하기 위한 리스트
check = [[0 for _ in range(M)] for _ in range(N)]

# 현재 위치 방문 체크
check[x][y] = 1

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

# 왼쪽으로 회전
def turn_left():
    global dir
    dir = (dir + 3) % 4

# 시뮬레이션 시작
count = 1
turn_time = 0

while(1):
    # 왼쪽으로 회전
    turn_left()
    nx = x + dx[dir]
    ny = y + dy[dir]

    #회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
    if Map[nx][ny] == 0 and check[nx][ny] == 0:
        check[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue

    # 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
    else:
        turn_time += 1

    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4:
        nx = x - dx[dir]
        ny = y - dy[dir]

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

        # 뒤가 바다로 막혀있는 경우
        else:
            break

        turn_time = 0

# 정답 출력
print(count)