[알고리즘] 2615 오목

게시물을 작성하면서 복습하는 문제를 선정하는 기준은<solved.ac 티어 실버 2 (Silver 2) 이상>입니다.

※ 본 사진과 해당 게시글 내용의 문제 모두 백준 : 온라인 저지[Baekjoon_OnlineJudge]사이트에서 발췌해왔습니다.


❓ 문제

<문제>
오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 
바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 
가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 
세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 
여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 
즉, 위의 그림은 검은색이 이긴 경우이다. 
하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.

입력으로 바둑판의 어떤 상태가 주어졌을 때, 
검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 

단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 
입력으로 들어오지 않는다.


<입력>
19줄에 각 줄마다 19개의 숫자로 표현되는데, 
검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 
숫자는 한 칸씩 띄어서 표시된다.

<출력>
첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 
검은색 또는 흰색이 이겼을 경우에는 

둘째 줄에 연속된 다섯 개의 바둑알 중에서 
가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의
가로줄 번호와, 세로줄 번호를 순서대로 출력한다.


❗ 풀이

My Code

# Case 1

메모리 : 30860KB
시간 : 76ms

우선 입력값으로 주어진 오목판 상황을 만들어 준다.

19x19 규격의 오목판이기 때문에
range(19)를 통해
2차원 배열로 만들어준다.

그 다음,
대각선/가로/세로를 이동하면서 연속적으로 계산해야하기 때문에

코드에서 좌표이동을 위해 사용할
dx, dy를 만들어준 후,

이중 for문으로
오목판의 첫번째 위치 ((0,0))부터 오목돌을 탐색한다.

여기서 주의해야할 점이
" 첫번째 위치에서부터 오른쪽 & 아래 방향으로 탐색 " 하기 때문에
[왼쪽 위 대각선], [윗쪽 직선], [오른 쪽 위 대각선], [왼쪽 직선] 의 이동 경우는 고려하지 않는다.

import sys
omok = []
for i in range(19):
    omok.append(list(map(int, sys.stdin.readline().split())))
dx = [0, 1, 1, -1] 
dy = [1, 0, 1, 1]
for x in range(19):
    for y in range(19):
        if omok[x][y] != 0:
            focus = omok[x][y]
            for i in range(4):
                cnt = 1
                nx = x + dx[i]
                ny = y + dy[i]
                while 0 <= nx < 19 and 0 <= ny < 19 and omok[nx][ny] == focus:
                    cnt += 1
                    if cnt == 5:
                        if 0 <= x - dx[i] < 19 and 0 <= y - dy[i] < 19 and omok[x - dx[i]][y - dy[i]] == focus:
                            break # 다시 for문 도세요~
                        if 0 <= nx + dx[i] < 19 and 0 <= ny + dy[i] < 19 and omok[nx + dx[i]][ny + dy[i]] == focus:
                            break 
                        print(focus)
                        print(x + 1, y + 1)
                        sys.exit(0)
                    nx += dx[i]
                    ny += dy[i]

print(0)

0이 아닌 값
즉, 흰돌이거나 검은 돌일 경우를 기점으로
한 줄에 5개의 같은 알이 놓여져 있는지 탐색하기 시작한다.

앞서 설정한 4가지 이동에 대한 경우의 수에 대해
4번의 for문을 돌리는데

이동 경우에 대한
다음 탐색 대상의 좌표를 nxny로 설정하고

"""
① 오목판의 범위를 벗어나지 않는 경우
② 탐색 기준돌과 같은 색인 경우

"""

위 2 경우가 모두 해당될 경우 동안
해당 방향으로
5개 연속 여부 탐색 을 하게끔 한다.

if cnt == 5 : 5개의 돌이 연속되었을 경우에
두 개의 if문으로 break 조건을 걸게된 이유는

위 문제를 살펴보면
" 6알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다. "라는 예외 조건이 있기 때문에
while문을 시작하게 된
첫 위치에서
6알 이상인지 아닌지 확인하려고
역방향으로 한칸씩 조사해 보는 것이다.

이 두 예외 경우 처리하는 조건문도 통과했다면
딱 다섯 알로 이긴 돌 이기 때문에
첫 시작돌 위치를 출력하고
돌아가고 있던 모든 작업들을 종료(sys.exit()) 시킨다.

마지막으로
못찾았을 경우에 출력할
print(0)도 작성해준다.

좋은 웹페이지 즐겨찾기