브루트 포스 알고리즘
뭔가 이름부터 대단한 알고리즘 같아 보이지만,
직역하면 무지막지한 힘, 의역하자면 계산 노가다로 풀이될 수 있다.
가장 쉽고 대표적인 브루트 포스의 예는 자물쇠 비밀번호 푸는 방법이다.
자물쇠 비밀번호를 알아내는데 브루트 포스를 어떻게 적용하냐면
0000~9999부터 하나씩 숫자를 바꿔주면서 확인하는 것이다.
간단한 알고리즘인 만큼 장점과 단점이 명확하다.
조건에 따라 엄청난 비효율성을 보인다는 것과 조건만 맞춰준다면 100%의 정확성을 보여준다는 것이다.
이번에 코테 문제를 풀면서 처음 알게된 브루트 포스, 어떻게 적용했는지 알아보자.
백준 2615. 오목
문제
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다
위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.
입력
19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.
출력
첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.
풀이
- 일단 주어진 조건부터 정리하자.
입력값 : 행과 열이 19로 고정된 이차원 배열
행렬을 탐색하면서 값이 5번 연속될 경우를 찾아 값과 인덱스를 반환해야 함
단, 5번을 초과해서는 안 됨
- 입력값을 정의하자.
# 오목판의 가로 세로 길이
length = 19
# 입력 값을 2차원 배열로 변환
b = [(list(map(int, input().split()))) for _ in range(length)]-
조건에서 경우의 수를 따져보자.
오목이 성립될 경우는 크게 가로로 5개, 세로로 5개, 대각선으로 5개 -> 3가지에 대각선의 경우 우하향, 우상향 두가지 경우로 나뉘니 총 4개의 경우의 수가 있다. -
경우의 수를 코드로 표현해보자.
2차원 배열을 y축 x축으로 그래프화 하고,
4가지 경우의 수를 변위(delta)값을 나태내어 보면 아래와 같다.
# 방향 = →,↓,↘,↗
delta = [(0,1), (1,0), (1,1), (-1,1)]- 이제 2차원 배열을 순회하면서 돌을 찾아보자.
for x in range(19):
for y in range(19):
if board[x][y] != 0:
stone = board[x][y]
# ...돌이 놓인 좌표를 1 또는 2로 표현하기로 했으니,
값이 0이 아닌 좌표 == 돌이 놓인 좌표이므로
변수 stone에 돌의 색깔을 표시한다.
- 돌을 찾았다면, 이 돌을 시작점으로 탐색을 한다.
for i in range(len(delta)):
dx, dy = delta[i]
count = 1
nx = x + dx
ny = y + dy
# ... 우선 뻗어나갈 수 있는 경우의 수가 네 개(→,↓,↘,↗)이므로 방향에 따른 변위값을 계속 더해주면서 새로운 좌표를 만든다.
- 새로운 좌표가 오목판의 범위를 벗어나지 않으면서 + 시작점과 돌의 색깔이 같다면 count를 증가시킨다.
while 0 <= nx < length and 0 <= ny < length and board[nx][ny] == stone:
count += 1
# ...- 카운트가 5가 되면, 육목 여부를 체크해준다.
while 0 <= nx < length and 0 <= ny < length and board[nx][ny] == stone:
count += 1
# 육목 여부 체크
if count == 5:
if 0 <= x - dx < length and 0 <= y - dy < length and board[x - dx][y - dy] == stone:
break
if 0 <= nx + dx < length and 0 <= ny + dy < length and board[nx + dx][ny + dy] == stone:
break인덱스 에러 방지를 위해 범위를 지정하고, 각각 시작점 직전의 좌표와 끝점 직후의 좌표에 같은 색의 돌이 있는지 체크한다.
- 육목 방지턱을 통과했다면, 해당 색깔에 해당하는 숫자와 좌표를 출력하고 함수를 종료시킨다.
while 0 <= nx < length and 0 <= ny < length and board[nx][ny] == stone:
count += 1
if count == 5:
if 0 <= x - dx < length and 0 <= y - dy < length and board[x - dx][y - dy] == stone:
break
if 0 <= nx + dx < length and 0 <= ny + dy < length and board[nx + dx][ny + dy] == stone:
break
# 육목이 아니라면 출력 후 리턴
print(stone)
print(x + 1, y + 1)
return바둑판은 1,1부터 시작하지만 배열은 0,0부터 시작하기 때문에 1씩 더해줌!
- count +=1의 결과가 아직 5가 아니라면, 같은 방향의 변위를 더 해주면서 계속 탐색한다.
while 0 <= nx < length and 0 <= ny < length and board[nx][ny] == stone:
count += 1
if count == 5:
if 0 <= x - dx < length and 0 <= y - dy < length and board[x - dx][y - dy] == stone:
break
if 0 <= nx + dx < length and 0 <= ny + dy < length and board[nx + dx][ny + dy] == stone:
break
print(stone)
print(x + 1, y + 1)
return
# 카운트가 5가 될 때까지 탐색
nx += dx
ny += dy새 좌표의 돌 색깔이 시작점과 다를 경우 while문 탈출하고 다른 방향의 변위 값을 가지고 다시 탐색한다.
전체 코드
length = 19
b = [(list(map(int, input().split()))) for _ in range(length)]
def find_omok_winner(board):
delta = [(0, 1), (1, 0), (1, 1), (-1, 1)]
for x in range(19):
for y in range(19):
if board[x][y] != 0:
stone = board[x][y]
for i in range(len(delta)):
dx, dy = delta[i]
count = 1
nx = x + dx
ny = y + dy
while 0 <= nx < length and 0 <= ny < length and board[nx][ny] == stone:
count += 1
if count == 5:
if 0 <= x - dx < length and 0 <= y - dy < length and board[x - dx][y - dy] == stone:
break
if 0 <= nx + dx < length and 0 <= ny + dy < length and board[nx + dx][ny + dy] == stone:
break
# break 가 안 걸린 경우 오목 -> 출력 후 종료
print(stone)
print(x + 1, y + 1)
return
nx += dx
ny += dy
print(0)
find_omok_winner(b)
