문제
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.
위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.
입력
19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.
출력
첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.
문제 접근
해당문제는 단순한 bfs와 다른 점이 몇가지 존재합니다.
- 상하좌우로만 움직이지 않는다.
- 일반적으로 보이는 bfs문제와 달리 해당 문제는 대각선이라는 방향이 존재합니다.
- 단순히 방향으로 움직이는 것이 아니라 하나의 방향 집합으로 움직여야한다.
- 해당 문제는 상하,좌우,왼쪽대각선,오른쪽대각선 이렇게 집합으로 움직여야합니다.
집합으로 움직이는 이유
오목은 같은 방향의 돌이 5개가 연달아 있을때 승리하게 됩니다. 때문에 위 그림과 같이 방향을 묶는 것이 아니라 이전에 탐색했던 돌과 같은 방향인지만 확인하면 된다라고 생각할수 있습니다.
하지만 해당 경우는 6목일때 문제가 발생합니다. 다음그림은 6목이기 때문에 승리조건에 어긋나지만 한방향으로 탐색하게 된다면 5목인 경우가 발생하기 때문에 잘못된 결과가 발생하게 됩니다.
저는 해당 문제를 해결하기위해 방향 집합 이전에 이런 생각을 해봤습니다. 위에서부터 차근차근 탐색한다면 어차피 오목 돌의 맨 끝자리이니 6목일 경우에는 더이상 탐색하지 않도록 visit 리스트를 만들어 방문 처리를 해야겠다!! 라고 생각도 했습니다. 하지만 이 경우에는 또 다른 예외가 발생합니다.
해당 예시를 보면 이미 방문처리를 할경우 5목을 만들었지만 중간에 방문표시가 존재해 돌의 개수를 셀때 문제가 발생합니다.
방향을 집합으로 어떻게 묶었는가...
dy = [-1,0,-1,-1,1,0,1,1] # 방향 상,좌,왼쪽위,오른쪽위 , 하,우,오른쪽아래,왼쪽위
dx = [0,-1,-1,1,0,1,1,-1]먼저 저는 방향을 상하,좌우,왼쪽대각선,오른쪽대각선으로 나눴습니다.
dy는 y축 다른말로 행의 의미를 가지고 있고 dx는 x축 열을 뜻합니다.
for di in range(4):
bfs(li[i][j],i,j,di)상하,좌우,왼쪽대각선,오른쪽대각선 해당 집합중 하나를 선택
for i in range(2):
ny = y+dy[di+i*4]
nx = x+dx[di+i*4]선택한 집합이 현재 인덱스 4개 차이로 나누어져있으니 dy[di+i*4] 를 통해 양방향 탐색을 진행해줬습니다.
[[-1,1],[0,0],[-1,1],[0,1]] [상하,좌우,왼쪽위 오른쪽아래,오른쪽위 왼아래]
[[0,0],[-1,1],[-1,1],[1,-1]] [상하,좌우,왼쪽위 오른쪽아래,오른쪽위 왼아래]
저는 위와 같이 집합처리를 했지만 지금 생각해보니 이렇게 집합을 나누는게 더 깔끔해 보이네요..😅
코드
li=[]
for i in range(19):
li.append(list(map(int,input().split())))
def bfs(now,y,x,di):
global count
check[y][x]=1
count+=1
loc.append([y,x])
for i in range(2):
ny = y+dy[di+i*4]
nx = x+dx[di+i*4]
if 0<=ny<19 and 0<=nx<19:
if check[ny][nx]==0 and li[ny][nx]==now:
bfs(now,ny,nx,di)
dy = [-1,0,-1,-1,1,0,1,1] # 방향 상하,좌우,왼대각,오대각
dx = [0,-1,-1,1,0,1,1,-1]
now,count=0,0
loc=[]
for i in range(19):
for j in range(19):
if li[i][j]>0:
for di in range(4):
check=[[0]*19 for _ in range(19)] # 무한 방문 안하도록 방문확인
count=0 # 돌의 개수 카운트
loc=[] # 현재 방문한 돌들의 위치
bfs(li[i][j],i,j,di)
if count==5:
now=li[i][j] # 만약 돌이 5개면 현재 돌의 색상 저장
break
if count==5:
break
if count==5:
break
loc.sort(key=lambda x : x[1]) # 왼쪽 첫번째로 정렬
print(now)
if len(loc)==5:
print(loc[0][0]+1,loc[0][1]+1)