[알고리즘] 구현 : 시뮬레이션과 완전 탐색

공부 : 동빈나 유튜브 <2. 그리디 & 구현 >+ 책 < 이것이 취업을 위한 코딩테스트다 >

 

구현(Implementation) : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

- 흔히 알고리즘 대회에서는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭

 

완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

예제 4 - 1 상하좌우

#여행가 A가 N*N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
#일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로도 분류됨

 

직접 작성한 코드에서 수정할 부분

 

 

- (답안) if문-elif문으로 반복되는 부분을 list로 만들어 간단하게 작성 가능

 

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

x, y = 1, 1

for direction in move:
    for i in range(len(move_types)):
        if direction == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    #공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or ny > n or ny > n:
        continue
    x, y = nx, ny

print(x, y)

 

예제 4 - 2 시각

# 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수 구하기

 

직접 작성한 코드에서 수정할 부분

 

 

- 이 문제는 3중 for문을 돌리면 모든 경우가 86400가지로 경우의 수가 작은 편이라 완전탐색 가능

- (답안)문자열과 in을 사용해 간단하게 확인 가능

 

for i in range(N + 1):
    for j in range(60):
        for k in range(60):
        	if '3' in str(i)+str(j)+str(k):
            	cnt += 1
            #if i % 10 == 3 or j // 10 == 3 or j % 10 == 3 or k // 10 == 3 or k % 10 == 3:
            #    cnt += 1

 

실전 문제 - 왕실의 나이트

# 나이트는 이동을 L모양으로 한다.
# 나이트가 이동할 수 있는 경우의 수 출력

 

직접 작성한 코드

- 움직일 수 있는 좌표값을 미리 리스트에 넣어둔다.- 숫자값도 리스트로 저장- 입력받은 좌표는 모두 숫자로 변경한다.

 

y_s, x_s = list(input())
y_s = ord(y_s) - ord('a') + 1
x_s = int(x_s)

move = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2), (1, 2)]
numList = [i for i in range(1, 8+1)]
result = 0

for x, y in move:
    if x_s + x in numList and y_s + y in numList:
        result += 1

print(result)

 

실전 문제 - 문자열 재정렬

# 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤
# 그 뒤에 모든 숫자를 더한 값을 이어서 출력

 

직접 작성한 코드에서 수정할 부분

 

 

- 만약 숫자가 아무것도 입력되지 않았다면 0을 출력하면 안되는데 출력한다. (수정필요)

- 답안에서 참고할 부분 --> join을 써서 리스트를 문자열로 변환하여 출력

 

alpha.sort()
if sum != 0:
    alpha.append(str(sum))

print(''.join(alpha))

 

 

실전 문제 - 게임 개발

 

<입력>

4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1

 

- 처음에 문제에 대한 이해를 잘못 해서 수정

- 네 방향 모두 갈 수 없는 경우 뒤쪽 방향으로 이동한다는 것을 잘못 이해

- 실제 서있는 방향에서 뒤로 갈 수 있다면 이동한다는 것을 의미

- 뒤로 이동 후 1단계로 돌아간다는 것을 구현하지 않아서 다시 수정

- 입력 예시가 2개 실행해봐서  맞았는지 확신할 수 없음

# 게임 개발
# N * M 크기의 직사각형 / 각각의 칸은 육지 또는 바다 / 캐릭터는 동서남북 중 한 곳을 바라봄
# 맵의 각 칸 (A, B) / A:  북쪽으로부터 떨어진 칸 개수, B: 서쪽으로부터 멀어진 칸의 개수
# 바다로 되어있는 공간은 갈 수 없다.

# 0 : 북쪽, 1 : 동쪽, 2 : 남쪽, 3 : 서쪽
move = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def visited_map(game_map, x, y, direction, visited, cnt):
    count = 0
    while True:
        while count < 4:
            print(x, y, direction)
            count += 1
            direction = (direction + 3) % 4  # 왼쪽 방향
            dx = move[direction][0]
            dy = move[direction][1]
            try:
                if visited[x + dx][y + dy] is False:  # 왼쪽방향 안가봤으면
                    visited[x + dx][y + dy] = True
                    cnt += 1
                    x = x + dx
                    y = y + dy
                    count = 0
            except:
                continue
        try:
            if visited[x - dx][y - dy] is True:
                if game_map[x - dx][y - dy] == 1:
                    break
                else:
                    x = x - dx
                    y = y - dy
                    count = 0
        except:
            break
    return cnt


N, M = map(int, input().split())
print(N, M)
firstX, firstY, direction = map(int, input().split())
print(firstX, firstY, direction)
cnt = 1

game_map = []
visited = []
for i in range(N):
    game_map.append(list(map(int, input().split())))
    visited.append([bool(int(x)) for x in game_map[i]])  # 외우자

visited[firstX][firstY] = True
print(visited_map(game_map, firstX, firstY, direction, visited, cnt))