오목
문제
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 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문제 해석
주의
- 6목일 경우
- 6목과 5목이 한번 이상씩 나온 경우
- index를 출력할 때 좌,상 을 선으로 생각
- 만약 가로줄이 답이면 가장 왼쪽 index
- 만약 세로줄이 답이면 가장 위쪽 index
- 만약 왼쪽 대각선줄이 답이면 가장 왼쪽 index
- 만약 오른쪽 대각선줄이 답이면 가장 왼쪽 index
이것들만 주의한다면 문제 푸는데 어려움이 없다.
풀이
-
흰색 돌이 나오는 경우 전부 흰색 queue에 append
-
검은색 돌이 나오는 경우 전부 검은색 queue에 append
- 여기서 append하는 요소는 index와 어느 방향으로 갈지에 관한 숫자, 총 돌이 몇개 나왔는지를 세주는 count
-
bfs 선언
- 흰색 돌인지, 검은색 돌인지 체크
- queue가 빌때까지 루프
- 방향이 아직 안정해져있다면?
- 가로 체크 오른쪽으로만
- 세로 체크 밑으로만
- 왼쪽 대각선 체크 왼쪽 밑으로만
- 오른쪽 대각선 체크 오른쪽 밑으로만
- 만약 업데이트한 좌표가 범위안에 존재한다면?
- 그곳의 값이 해당 색의 돌과 같다면?
- 각 루트마다 업데이트 하기 전 경로 돌이 존재하는지 체크
- 무슨 말이냐면 5목을 세기 위한 첫 시작돌이 맞는지 체크
- 1 2 3 4 5 이런식으로 돌이 있으면 1번 돌이 시작돌임
- 그런데 2번 돌도 시작돌로 간주할 수 있기 때문에 2번 돌 이전 돌이 color_num과 같은지 체크하는 것
- skip 하기 위해 continue
- 존재 안한다면? 즉, 시작돌이라면?
- 다음 경로의 돌의 index와 어떤 루트로 갈 것인지에 대한 숫자, count 값을 넣어준다.
- 시작 돌이라면 다음 돌을 찾았을 경우 돌이 2개 존재하는 것이기에 count를 2로 준것.
- 그곳의 값이 해당 색의 돌과 같다면?
- 방향이 정해져있다면?
- 루트에 맞게 다음 경로 업데이트
- 만약 업데이트한 좌표가 오목판 안에 존재한다면?
- 업데이트한 좌표에 color_num과 맞는 돌이 존재한다면?
- count가 5라면?
- 6목을 방지하기 위해 continue
- 5가 아니라면?
- queue에 append
- count가 5라면?
- 업데이트 좌표에 돌이 존재 안한다면?
- 5개가 끝이기 때문에 5목
- ans에 좌표들과 루트, count 넣어줌
- 왜 좌표에 1씩 더해주냐면 우리는 index가 0부터 시작하지만, 출력할 때에는 1부터 시작하는 것으로 생각해야 하기 때문
- 업데이트한 좌표에 color_num과 맞는 돌이 존재한다면?
- 업데이트한 좌표가 오목판 안에 존재 안한다면?
- count가 5라면?
- 5목이기 때문에 ans에 삽입
- count가 5라면?
- 방향이 아직 안정해져있다면?
-
흰돌과 검은돌을 전부 bfs를 돌린다.
-
ans에 쌓인 값들을 보면서 아무것도 안쌓였다면 승부가 안난것이고
-
흰색 ans에 쌓여있으면 흰색 승리
-
검은색 ans에 쌓여있으면 검은색 승리
-
각 루트에 맞게 좌상선으로 생각해서 index 수정 후 출력
import sys
from collections import deque
omok = [[0] * 19 for _ in range(19)]
for i in range(19):
omok[i] = list(map(int, sys.stdin.readline().split()))
queue_white = deque()
queue_black = deque()
for i in range(19):
for j in range(19):
if omok[i][j] == 2:
queue_white.append([i, j, 0, 1])
elif omok[i][j] == 1:
queue_black.append([i, j, 0, 1])
# 0 : 아직 방향이 안정해져있음
# 1 : 가로 체크 오른쪽으로만
# 2 : 세로 체크 밑으로만
# 3 : 왼쪽 대각선 체크 왼쪽 밑으로만
# 4 : 오른쪽 대각선 체크 오른쪽 밑으로만
dx = [0, 1, 1, 1]
dy = [1, 0, -1, 1]
def bfs(queue, color):
ans = []
if color == "white":
color_num = 2
else:
color_num = 1
while queue:
x, y, route, count = queue.popleft()
if route == 0:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
route_check = i + 1
if 0 <= nx <= 18 and 0 <= ny <= 18:
if omok[nx][ny] == color_num:
if route_check == 1:
if 0 <= y - 1:
if omok[x][y - 1] == color_num:
continue
elif route_check == 2:
if 0 <= x - 1:
if omok[x - 1][y] == color_num:
continue
elif route_check == 3:
if 0 <= x - 1 and y + 1 <= 18:
if omok[x - 1][y + 1] == color_num:
continue
elif route_check == 4:
if 0 <= x - 1 and 0 <= y - 1:
if omok[x - 1][y - 1] == color_num:
continue
queue.append([nx, ny, route_check, 2])
else:
nx = x + dx[route - 1]
ny = y + dy[route - 1]
if 0 <= nx <= 18 and 0 <= ny <= 18:
if omok[nx][ny] == color_num:
if count == 5:
continue
queue.append([nx, ny, route, count + 1])
else:
if count == 5:
ans.append([x + 1, y + 1, route, count])
elif count == 5:
ans.append([x + 1, y + 1, route, count])
return ans
ans_black = bfs(queue_black, "black")
ans_white = bfs(queue_white, "white")
black_win = []
white_win = []
if len(ans_black) != 0:
for i in range(len(ans_black)):
if ans_black[i][3] == 5:
if ans_black[i][2] == 1:
black_win.append((ans_black[i][0], ans_black[i][1] - 4))
elif ans_black[i][2] == 2:
black_win.append((ans_black[i][0] - 4, ans_black[i][1]))
elif ans_black[i][2] == 3:
black_win.append((ans_black[i][0], ans_black[i][1]))
else:
black_win.append((ans_black[i][0] - 4, ans_black[i][1] - 4))
if len(ans_white) != 0:
for i in range(len(ans_white)):
if ans_white[i][3] == 5:
if ans_white[i][2] == 1:
white_win.append((ans_white[i][0], ans_white[i][1] - 4))
elif ans_white[i][2] == 2:
white_win.append((ans_white[i][0] - 4, ans_white[i][1]))
elif ans_white[i][2] == 3:
white_win.append((ans_white[i][0], ans_white[i][1]))
else:
white_win.append((ans_white[i][0] - 4, ans_white[i][1] - 4))
if len(black_win) != 0:
print("1")
print(*black_win[0])
elif len(white_win) != 0:
print("2")
print(*white_win[0])
else:
print("0")
고찰
- 실버 문제라기에는 예외가 생각보다 많았다.
- 이 문제도 초반에 설계만 잘 하고 들어가면 시간을 많이 줄일 수 있을것 같다.
항상 성장하는 개발자 최동혁입니다.