[ baekjoon ] 비숍 1799번 ( python, java )

문제

백준 1799 비숍 풀이 ( 자바, 파이썬 )

www.acmicpc.net/problem/14712www.acmicpc.net/problem/1799

1799번: 비숍

 

 

풀이

이 문제에 적용한 핵심

1. 일단 color를 구분하는 color 2차 리스트(배열)을 만들었다. 비숍 특성상 흰 칸에 있는 비숍은 검은 칸에 있는 비숍에 영향을 주지 않으므로 효율성을 위해 각각 구분해서 리스트(배열)를 만들어 구해준다. 나는 검은칸을 1(true), 흰 칸을 0(false)로 생각하고 진행했다.

2. isused의 사용

코드를 보면 isused라는 리스트(배열)이 있는데 isused01의 예를 들어보면

예를 들어 비숍이 0,2에 있을 때 isused01[x+y] 즉 isused[0+2]에 해당하는

빨간점들은 True로 처리하게 되면 체스판의 1값이 1,1에 있다고 하더라도 0,2에서 이미 True 처리를 했으므로 isused01[2]가 True이므로 1,1에는 비숍을 놓을 수 없게된다.

즉, 같은 직선에 놓여 있는 경우라고 생각하면 된다.

 

마찬가지로 반대방향 대각선은

isused02로 처리했는데 반대 대각선의 경우는 isused[x-y+n-1]이다. 같은 원리로 생각하면 된다.

 

 

이제 코드를 보면

fun의 파라미터 index(자바는 solution)는 각 black과 white의 원소를 하나씩 확인한다.

• python 풀이

n=int(input())

chess_map=[]
black=[]
white=[]
color=[[0]*n for _ in range(n)]

for i in range(n):
    for j in range(n):
        color[i][j]=(i % 2 == 0 and j % 2 == 0) or (i % 2 != 0 and j % 2 != 0)

for i in range(n):
    chess_map.append(list(map(int, input().split())))
    for j in range(n):
        # True가 검은색
        if chess_map[i][j]==1 and color[i][j]==1:
            black.append((i,j))
        # False가 흰색
        if chess_map[i][j]==1 and color[i][j]==0:
            white.append((i,j))

# 검은색인 경우
Bcnt=0
# 흰색인 경우
Wcnt=0

isused01=[0]*(n*2-1)
isused02=[0]*(n*2-1)

def fun(bishop,index,count):
    global Bcnt, Wcnt
    if index==len(bishop):
        rx,ry=bishop[index-1]
        # 블랙이면 Bcnt 최대값
        if color[rx][ry]:
            Bcnt=max(Bcnt,count)
        # 흰색이면 Wcnt 최대값
        else:
            Wcnt=max(Wcnt,count)
        return

    x,y=bishop[index]
    if isused01[x+y] or isused02[x-y+n-1]:
        fun(bishop,index+1,count)
    else:
        isused01[x+y]=1
        isused02[x-y+n-1]=1
        fun(bishop,index+1,count+1)
        isused01[x+y]=0
        isused02[x-y+n-1]=0
        fun(bishop,index+1,count)

if len(black)>0:
    fun(black,0,0)
if len(white)>0:
    fun(white,0,0)
print(Bcnt+Wcnt)

 

 

• Java 풀이

package study;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class baek1799 {
	static int N, M;
	static int[][] map;
	static int[] isused01;
	static int[] isused02;
	static int leng;
	static int Bcnt = 0;
	static int Wcnt = 0;
	static ArrayList<Pair> white;
	static ArrayList<Pair> black;
	static boolean[][] color;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];

		white = new ArrayList<>();
		black = new ArrayList<>();
		color = new boolean[N][N];
		isused01 = new int[N * 2 - 1];
		isused02 = new int[N * 2 - 1];

		

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				color[i][j] = (i % 2 == 0 && j % 2 == 0) || (i % 2 != 0 && j % 2 != 0);
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1 && color[i][j] == true) {
					black.add(new Pair(i, j));
				}
				if (map[i][j] == 1 && color[i][j] == false) {
					white.add(new Pair(i, j));
				}
			}
		}
		if( black.size()>0)
			solution(black, 0, 0);
		if( white.size()>0)
			solution(white, 0, 0);

		System.out.println(Bcnt + Wcnt);
	}

	public static void solution(ArrayList<Pair> pair, int index, int count) {
		if (index == pair.size()) {
			int rx = pair.get(index - 1).first();
			int ry = pair.get(index - 1).second();
			if (color[rx][ry] == true)
				Bcnt = Math.max(Bcnt, count);
			else
				Wcnt = Math.max(Wcnt, count);
			// Wcnt = Math.max(Wcnt, count);
			return;
		}
		int x = pair.get(index).first();
		int y = pair.get(index).second();
		if (isused01[x + y] == 1 || isused02[x - y + N - 1] == 1) {
			solution(pair, index + 1, count);
		} else {
			isused01[x + y] = 1;
			isused02[x - y + N - 1] = 1;
			solution(pair, index + 1, count + 1);
			isused01[x + y] = 0;
			isused02[x - y + N - 1] = 0;
			solution(pair, index + 1, count);
		}

	}

}

class Pair {
	Integer y;
	Integer x;

	public Pair(Integer y, Integer x) {
		this.y = y;
		this.x = x;
	}

	public Integer first() {
		return y;
	}

	public Integer second() {
		return x;
	}

}