5️⃣ 오목
백준 Silver2
문제
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, … ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, … 19번의 번호가 붙는다.
위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.
입력
19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.
출력
첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.
예제 입력 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0
0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
예제 출력 1
1
3 2
📖 가져다 쓰기
브루트 포스를 사용하는 문제였다. 이 문제를 브루트 포스로 풀어도 되는 이유는 다음과 같다.
- 바둑판의 데이터 입력수는 19x19 = 361
이 문제는 N ≦ 500에 해당하므로 O(n^3)의 시간복잡도로 해결할 수 있고 브루트 포스는 이를 만족하기 때문에 나는 모든 위치를 탐색해보며 오목인지 아닌지를 판별하기로 결정하였다.
📐 과정 설계/관리
1트
상하좌우, 대각선 8방향을 탐색하며 같은 색의 돌을 만날 경우 count를 증가시켜주며 5를 만족할 때만 승리 판정을 짓는다.
하지만 이 경우에는 형광펜과 같이 꺾인 오목의 반례가 생긴다.
2트
(1,1)부터 (N,N)까지 모든 위치를 탐색해보며 돌을 만났을 때 행,열,대각 3 부분을 검사하여 같은 색의 돌을 세준다.
그렇게 하여 count가 5인 것만 추린다. 이 경우 역시 어이없는 실수였는데 오목은 돌이 연속적으로 5개가 놓여야 하는데 이러한 설계는 불연속적인 5개도 포함시키므로 틀린다.
3트
내가 이 문제에서 간과했던 부분은 오목의 좌선상선을 출력해야 한다는 점이다.
따라서 8방향 탐색이 아닌 ↗️ ➡️ ↘️ ⬇️ 의 4방향만 탐색해야 좌선상선 조건을 만족시킬 수 있다.
나는 코드 구현을 할 때 while 문 중간에 count=5가 되었을 때 탈출하는 방식이 아닌 while 문이 다 끝나고 최종적인 count를 보아서 5일 때만 승리 판정을 짓도록 했다. 그래서 따로 육목검사는 안해도 된다고 생각하였는데 반례가 있었다.
최종적으로 오목의 시작 이전 돌을 검사해보는 코드를 추가하여 통과하였다.
👨🏻💻 CODE
import sys
input = sys.stdin.readline
omok = []
for i in range(19):
omok.append(list(map(int,input().split())))
dx = [-1,0,1,1]
dy = [1,1,1,0]
for i in range(19):
for j in range(19):
color = omok[i][j]
if color != 0:
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
if 0<=nx<19 and 0<=ny<19 and omok[nx][ny] == color:
count = 2
a = dx[k]
b = dy[k]
while 0<=nx+a<19 and 0<=ny+b<19 and omok[nx+a][ny+b] == color:
count += 1
a += dx[k]
b += dy[k]
# if (i,j) == (4,1):
# print("카운트: {0}, 방향: {1},{2}".format(count, dx[k],dy[k]))
if count == 5:
# 육목 체크
if (i-dx[k] < 0 or j-dy[k] < 0) or omok[i-dx[k]][j-dy[k]] != color:
print(color)
print(i+1,j+1)
sys.exit(0)
print(0)
