백준4278 Go [python]

문제링크 https://www.acmicpc.net/problem/4278

문제

원문은 영어이므로 번역을 해봤습니다.

 

바둑은 가로 및 세로 선이 홀수 개인 정사각형 보드에서 플레이됩니다. 일반적인 보드 크기는 9x9, 13x13, 19x19입니다. 하지만 여기에서는 보드의 크기를 3 ≤ n ≤ 19인 N x N 크기로 가정합니다.

 

검은 돌(흑)과 흰 돌(백)은 번갈아가며 두 선이 교차하는 지점에 돌을 놓습니다. 흑이 먼저 시작합니다. 언제든지 한 플레이어는 돌을 놓지 않고 패스할 수 있습니다. 하지만 두 플레이어가 연속으로 패스하면 게임이 종료됩니다. 돌을 놓는 동작은 P(x,y)로 나타내며, 여기서 P는 흑의 경우 B, 백의 경우 W로 나타내고, (1-n)/2 ≤ x,y ≤ (n-1)/2는 돌을 놓을 격자 위치를 나타냅니다. 보드의 중앙 교차점의 좌표는 (0,0)입니다.

 

바둑의 규칙은 비교적 간단하지만, 전략의 미묘함이 게임을 매우 도전적으로 만듭니다. 다음 규칙을 사용해야 합니다.

 

 

• 흑이 먼저 플레이합니다.
• 흑과 백은 번갈아 가며 돌을 놓으며, 각 턴에 플레이어는 돌을 놓거나 패스할 수 있습니다. 두 플레이어가 연속으로 패스하면 게임이 종료됩니다.
• 돌은 비어 있는 교차점에만 놓을 수 있습니다.
• 플레이어 P가 돌을 놓아 자신의 돌과 보드의 가장자리가 연결된 상태로 상대방 Q의 돌이 있는 연결된 영역을 완전히 둘러싸면, Q의 돌은 포획되어 보드에서 제거됩니다. 더 정확하게는 두 교차점이 수평 또는 수직(대각선 제외)으로 인접해 있을 때 연결되었다고 합니다. 어떤 영역이 P의 돌로 완전히 둘러싸여 있으면, 그 영역은 빈 교차점과 연결되지 않은 상태여야 합니다.
• P가 돌을 놓아 Q의 돌이 포획된 경우, P의 돌은 포획되지 않습니다.
• P의 돌로 둘러싸인 영역으로, Q의 돌이 없는 연결된 영역은 P의 소유로 간주됩니다.
• 플레이어 P의 점수는 최종 보드 상태에서 P가 소유한 빈 영역의 수와 게임 중에 P가 포획한 Q의 돌의 수를 더한 값입니다.

 

입력

입력은 여러 개의 테스트 케이스로 구성됩니다. 각 테스트 케이스는 N(보드 크기)과 M(게임 중 놓인 돌의 수)을 나타내는 한 줄로 시작합니다. 다음으로 m줄이 이어지며, 각 줄은 위에 설명한 형식의 돌 놓기 정보를 제공합니다. M은 돌을 놓은 횟수만을 계산하며,

패스는 두 번의 연속된 돌 놓기를 초래할 수 있습니다. 각 움직임은 항상 합법적인 움직임이라고 할수 있습니다. 각 테스트 케이스의 마지막 줄은 "0 0"으로 표시됩니다.

 

출력

각 테스트 케이스에 대해 흑의 점수와 백의 점수를 한 줄에 출력합니다.

 

 

문제 풀이

문제 풀이 아이디어

1. 입력을 받고 보드를 초기화 한다.

2. M번 만큼 3번~4번 작업을 반복 한다.

3. 흑/백이 돌을 놓는다. (입력 좌표를 수정한다.)

4. 상하좌우로 탐색하여 만약 돌을 잡을수 있다면 돌을 잡는다. 그렇지 않다면 넘어간다.

5. 흑,백의 점수를 계산하여 출력한다.

 

문제 아이디어 자체는 깔끔한편이다.

 

그래서 우리는 무엇을 구현해야하는가?

1. 돌을 놓는 작업

2. 돌을 잡는 함수

3. 점수를 계산하는 함수

 

구현

돌을 잡는 함수

돌을 잡는 함수를 구현을 해보기전에 어떠할때 이 함수를 호출할까를 생각해보자.

돌을 놓을때마다 모든돌에 대해서 확인 해볼까? -> 충분히 가능하나 시간이 오래걸린다.

그럼 돌을 놓은 위치에서 상하좌우의 돌만 잡을 수 있는지 확인할까? -> 좋은 접근!

 

그럼 어떨떄 이 함수를 호출했는지 알았다면 함수를 구현을 해야하는데 어떻게 구현할수 있을까 -> bfs

bfs를 활용하여 돌이 빈공간과 연결이 되어 있다면 잡히는 돌이 아니다라는걸 알수 있기 때문이다.

왜 빈공간과 연결 되어 있으면 잡히지 않는건 따로 생각을 해보기 바란다.

 

그럼 함수를 구현해보자

def bfs(board,v,x,y,t,K,N,W,B): # 보드, 방문 배열, 시작 x,y좌표, 탐색해야하는돌, 방문배열 저장수, 보드의 크기, W,B점수
    q=deque([(x,y)])
    p=True
    co=[(x,y)]
    v[y][x]=K
    while q:
        x,y=q.popleft()
        for dx,dy in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
            if 0<=dx<N and 0<=dy<N and v[dy][dx]<K:
                if board[dy][dx]==0:
                    p=False 
                    return board,v,W,B #빈공간과 연결 되어 있으면 잡지 못하므로 함수 종료
                if board[dy][dx]==t: #자신돌과 연결 되어 있으면 계속 탐색
                    q.append((dx,dy))
                    v[dy][dx]=K
                    co.append((dx,dy))
    if p: #잡을수 있다면 (빈공간과 연결되지 않음)
        if board[co[0][1]][co[0][0]]==2:
            W+=len(co) #잡은돌도 점수에 반영됨
        else:
            B+=len(co) #잡은돌도 점수에 반영됨
        for x,y in co:
            board[y][x]=0 #잡고 빈공간으로 만들기
    return board,v,W,B

 

점수를 계산 하는 함수

이 함수도 bfs를 활용하면 쉽게 점수를 구할수 있다.

 

아이디어 -> 빈공간을 bfs로 탐색한다. 만약 벽이 아닌 돌(흑,백)을 만들면 확인한다. 만약 이전에도 만났던 돌의 색과 같지 않다면 누구의 영역도 아니므로 점수를 올리지 않는다. 그렇지 않고 같은 돌로 벽이 이루어져있다면, 그 색의 영역이라고 할수 있다.

def sfs(V,S,board,N,W,B): #보드, 시작 x,y좌표, 보드, 보드크기, 흑백 점수
    q=deque([S])
    t=None #누구의 구역인지 저장하는 변수
    c=1 #빈공간의 크기
    k=True #점수 카운트를 해도 되나를 체크하는 변수
    V[S[1]][S[0]]=1
    while q:
        x,y=q.popleft()
        for dx,dy in [(x-1,y),(x+1,y),(x,y+1),(x,y-1)]:
            if 0<=dx<N and 0<=dy<N and not V[dy][dx]:
                if t==None and board[dy][dx] in (1,2): #최근에 발견했던 돌이 없고 빈공간이 아니라면
                    t = board[dy][dx] #최근 발견돌 저장
                if board[dy][dx]==0: #빈공간이면 큐에 담기
                    c+=1
                    q.append((dx,dy))
                    V[dy][dx]=1
                if t!=None and board[dy][dx]in(1,2) and board[dy][dx]!=t: #만약 최근에 발견했던 돌과 다른 돌을 발견하면 점수카운트를 하지 않음
                    k=False
    if k: #최근 발견돌이 한개의 색 이라면
        if t==1:
            W+=c
        else:
            B+=c
    return V,W,B

 

 

입력 처리

주요 함수를 모두 구현했다.

좌표를 처리하기 쉽게 바꿔야한다.

def process_coordinate(s):
    l='' #좌표 저장할 문자열 
    j=False
    for p in s:
        if p=='(': #괄호가 열리면 좌표 저장 시작
            j=True
        elif p==')': #괄호가 닫히면 저장된 좌표를 정수로 바꿔서 return
            x,y=map(int,l.split(','))
            t=1 if s[0]=='B' else 2
            return t,x,y
        elif j: #괄호가 열려있으면 문자열 저장
            l+=p

 

메인 함수

def main():
    while 1:
        W=B=0
        K=1
        N,M=map(int,input().split())
        if N==0:break # 0 0이 입력이면 프로그램 종료
        board=[[0]*N for _ in range(N)]
        v=[[0]*N for _ in range(N)]
        V=[[0]*N for _ in range(N)]
        w=N//2
        for z in range(M):
            a,x,y=process_coordinate(input().strip())
            board[y+w][x+w]=a
            h=1 if a==2 else 2
            if z>2:
                for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                    i,j=x+w+dx,y+w+dy
                    if 0<=i<N and 0<=j<N and board[j][i]==h:
                        board,v,W,B=bfs(board,v,i,j,board[j][i],K,N,W,B)
                        K+=1
        for i in range(N):
            for j in range(N):
                if board[j][i]==0 and not V[j][i]:
                    V,W,B=sfs(V,(i,j),board,N,W,B)
        print(W,B)
    
    return 1

 

 

전체 코드

from collections import deque
input=open(0).readline
def bfs(board,v,x,y,t,K,N,W,B):
    q=deque([(x,y)])
    p=True
    co=[(x,y)]
    v[y][x]=K
    while q:
        x,y=q.popleft()
        for dx,dy in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
            if 0<=dx<N and 0<=dy<N and v[dy][dx]<K:
                if board[dy][dx]==0:
                    p=False
                    return board,v,W,B
                if board[dy][dx]==t:
                    q.append((dx,dy))
                    v[dy][dx]=K
                    co.append((dx,dy))
    if p:
        if board[co[0][1]][co[0][0]]==2:
            W+=len(co)
        else:
            B+=len(co)
        
        for x,y in co:
            board[y][x]=0
    return board,v,W,B

def sfs(V,S,board,N,W,B):
    q=deque([S])
    t=None
    c=1
    k=True
    V[S[1]][S[0]]=1
    while q:
        x,y=q.popleft()
        for dx,dy in [(x-1,y),(x+1,y),(x,y+1),(x,y-1)]:
            if 0<=dx<N and 0<=dy<N and not V[dy][dx]:
                if t==None and board[dy][dx] in (1,2):
                    t= board[dy][dx]
                if board[dy][dx]==0:
                    c+=1
                    q.append((dx,dy))
                    V[dy][dx]=1
                if t!=None and board[dy][dx]in(1,2) and board[dy][dx]!=t:
                    k=False
    if k:
        if t==1:
            W+=c
        else:
            B+=c
    return V,W,B

def process_coordinate(s):
    l=''
    j=False
    for p in s:
        if p=='(':
            j=True
        elif p==')':
            x,y=map(int,l.split(','))
            t=1 if s[0]=='B' else 2
            return t,x,y
        elif j:
            l+=p

def main():
    while 1:
        W=B=0
        K=1
        N,M=map(int,input().split())
        if N==0:break
        board=[[0]*N for _ in range(N)]
        v=[[0]*N for _ in range(N)]
        V=[[0]*N for _ in range(N)]
        w=N//2
        for z in range(M):
            a,x,y=process_coordinate(input().strip())
            board[y+w][x+w]=a
            h=1 if a==2 else 2
            if z>2:
                for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                    i,j=x+w+dx,y+w+dy
                    if 0<=i<N and 0<=j<N and board[j][i]==h:
                        board,v,W,B=bfs(board,v,i,j,board[j][i],K,N,W,B)
                        K+=1
        for i in range(N):
            for j in range(N):
                if board[j][i]==0 and not V[j][i]:
                    V,W,B=sfs(V,(i,j),board,N,W,B)
        print(W,B)
    
    return 1  
main()

 

시간복잡도

 

• O(M * N^2) (돌을 놓으면서 발생하는 연산)
• O(N^2) (영역 점수 계산)

결과 O(M * N^2)

 

 

회고

문제는 무난한 난이도였다. 제일 어려웠던 부분은 돌잡기 함수 구현이었다.

시간은 밥먹으면서 ,아침자습시간, 쉬는시간에 시간내서 하다보니 2시간 정도 걸린것 같다.

 

 

문제 태그:

#그래프 이론, #그래프 탐색, #BFS, #구현