Study/알고리즘
[백준] 2615번_오목
혤리
2020. 2. 12. 23:32
문제 링크 : https://www.acmicpc.net/problem/2615
2615번: 오목
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림
www.acmicpc.net
import sys
dx = [0,1,1,1]
dy = [1,0,-1,1]
black = []; white = []
for i in range(1,20):
board = list(map(int,input().split()))
for j in range(len(board)):
if board[j] == 1:
black.append([i,j+1])
elif board[j] == 2:
white.append([i,j+1])
# black부터 찾아보자
for b1 in black:
r,c = b1
for d in range(4):
check_r , check_c = r,c
cnt = 1
while 0<=check_r<=19 and 0<=check_c<=19:
if [check_r+dx[d],check_c+dy[d]] in black:
cnt+=1
check_r += dx[d]; check_c += dy[d]
else:
break
if cnt>=5:
break
if cnt == 5:
if [check_r+dx[d],check_c+dy[d]] not in black:
if 1<= r-dx[d]<=19 and 1<=c-dy[d]<=19:
if [r-dx[d],c-dy[d]] not in black:
if d!=2:
print(1)
print(r,c)
sys.exit()
else:
print(1)
print(check_r,check_c)
sys.exit()
else:
if d!=2:
print(1);print(r,c),sys.exit()
else:
print(1);print(check_r,check_c),sys.exit()
# white를 찾아보자
for b1 in white:
r,c = b1
for d in range(4):
check_r , check_c = r,c
cnt = 1
while 0<=check_r<=19 and 0<=check_c<=19:
if [check_r+dx[d],check_c+dy[d]] in white:
cnt+=1
check_r += dx[d]; check_c += dy[d]
else:
break
if cnt>=5:
break
if cnt == 5:
if [check_r+dx[d],check_c+dy[d]] not in white:
if 1<= r-dx[d]<=19 and 1<=c-dy[d]<=19:
if [r-dx[d],c-dy[d]] not in white:
if d!=2:
print(2)
print(r,c)
sys.exit()
else:
print(2);print(check_r,check_c);sys.exit()
else:
if d!=2:
print(2);print(r,c),sys.exit()
else:
print(2);print(check_r,check_c);sys.exit()
print(0)
black과 white 인덱스를 받지 않고 board 받은 거에서 처리해주는게 메모리 낭비가 덜 할 것 같다.
또한 위의 코드는 (우측, 우측 하향 대각선, 하측, 좌측 하향 대각선)을 보며 탐색을 했는데 이러면 맨 왼쪽 인덱스를 출력하기 위해서 좌측 대각선으로 5개가 만들어질 때, 처음 시작했던 인덱스가 아닌 마지막 인덱스를 출력해주어야 한다.
따라서 (우측 상향 대각선, 우측, 우측 하향 대각선, 하측)을 보면 어느 방향에서 나왔든 상관없이 처음 인덱스만 출력해주면 된다.