[백준 | 골드1] 1799_비숍

 

일단 대각선 확인해서 없는 경우 비숍 다 넣을 수 있음

최대값은 아님

import sys
sys.stdin = open("20220715_백준_1799_비숍.txt", "r")

n = int(input())
board = []
max_bishop = 0
dx = [-1, 1, 1, -1]     #오른쪽 위 대각선, 오른쪽 아래 대각선, 왼쪽 아래 대각선, 왼쪽 위 대각선
dy = [1, 1, -1, -1]
position = []

#입력 받고, 비숍이 놓일 수 있는 자리(1)의 최대 개수를 카운트 하자
for i in range(n) :
    row = input().split()
    temp = []
    for j in row :
        b = int(j)
        temp.append(b)
        if b == 1 :
            max_bishop += 1
    board.append(temp)

def DFS(board, max_bishop, L, start_x, start_y, visited_map, position) :
    #종료조건 : 비숍이 놓일 수 있는 환경의 최대 치까지만 구해보자
    if L == max_bishop :
        return

    cross_flag = True                               #대각선에 비숍 있는지 체크
    #현재 지점(start_x, start_y)으로부터 4방향 대각선 체크
    for d in range(4) :
        next_x = start_x                                #현재 시작점 저장
        next_y = start_y
        # cross_flag = True                               #대각선에 비숍 있는지 체크
        
        #현재 시작점에서부터 대각선으로 뻗어 나가면서 비숍이 놓일수 있는 자리(1)인지
        #비숍이 놓여있는지 있는 자리(2) 확인
        while True :
            next_x = next_x + dx[d]                     #현재 시작점에서부터 뻗어나가면서 대각선 체크
            next_y = next_y + dy[d]

            #대각선 범위 초과인 경우 break
            if next_x < 0 or n-1 < next_x or next_y < 0 or n-1 < next_y: 
                break

            if board[next_x][next_y] == 2 :             #이미 비숍이 놓여서 놓일 수 없음
                cross_flag = False
                break
        
        #대각선에 이미 비숍이 한개라도 자리에 놓여있으면(2) 놓지 못한다
        if cross_flag is False :
            break

    #대각선에 비숍 없어서 비숍 놓을 수 있음 cross_flag == True
    #현재 자리가 1이라서 비숍 놓을 수 있음
    if cross_flag is True and board[start_x][start_y] == 1 :
        board[start_x][start_y] = 2             #시작 점에 비숍을 놓아본다.

    print(board)




def solution(n, board, max_bishop) :
    answer = 0
    visited_map = [[False] * n for _ in range(n)]
    position = []

    for i in range(n) :
        for j in range(n) :
            #비숍이 놓일 수 있는 자리인 경우 DFS
            if board[i][j] == 1 :
                DFS(board, max_bishop, 0, i, j, visited_map, position)

    return answer

print(solution(n, board, max_bishop))

#문제 정리
#대각선으로 움직일 수 있는 비숍
#1은 비숍이 놓일 수 있는 곳
#0은 비숍이 놓일 수 없는 곳