필기시험 프로 그래 밍: 고객 지원 배정 문제

고객 지원 관리 원 은 n 명의 고객 지원 아가 씨 를 관리 하고 있 습 니 다. 그 는 각 조 에 24 시간 당직 을 서 야 합 니 다. 간단하게 말하자면 각 조 에 두 명의 고객 센터 만 있 고 하루 에 1 명의 고객 센터 만 출근 해 야 한다 고 가정 합 니 다. 그리고 일부 고객 센터 는 어떤 이유 로 같은 날 에 출근 하지 못 하기 때문에 우 리 는 고객 센터 에 대해 번 호 를 매 겼 습 니 다. i (i > = 1 & i < = n) 개 조 의 고객 지원 번 호 는 2 * i - 1 과 2 * i 입 니 다.그리고 m 가지 다음 과 같은 제약 관 계 를 알 게 되 었 습 니 다. 고객 센터 번호 a 와 번호 b 는 같이 출근 할 수 없습니다. 관리 자 는 선택 하 세 요. 오늘 실행 가능 한 방안 이 있 는 지 판단 해 주세요. m 가지 제약 을 만족 시 킬 뿐만 아니 라 각 조 에 하나의 고객 센터 를 출근 시 킬 수 있 습 니 다.
입력: n (n 개 그룹 대표)
m: m 조 제약, 다음 m 줄 데이터 가 있 습 니 다.
a, b (대표 a b 두 고객 센터 레이 블 은 동시에 출근 할 수 없습니다)
출력: 실행 가능 한 지 여 부 를 판단 합 니 다. 출력 no 가 안 되면 출력 가능 yes
예:
입력:
4
3
1,4
2,3
7,3
출력: yes
 
설명: 이 는 깊이 있 는 우선 검색 으로 문 제 를 해결 할 수 있 지만 이미 선택 한 고객 센터 번 호 를 제약 조건 의 판단 에 저장 하기 위해 용 기 를 유지 해 야 합 니 다. 새로운 고객 센터 번 호 를 저장 할 때마다 제약 이 성립 되 는 지 여 부 를 판단 합 니 다. 만약 에 성립 되 고 다음 그룹 에 들 어가 지 않 으 면 방금 입력 한 번 호 를 삭제 하고 이전 층 으로 돌아 갑 니 다.
 
import java.util.ArrayList;
import java.util.Scanner;

public class Test{
	
	public static void main(String[] args) {
		 Scanner sca = new Scanner(System.in);
		 //  、     、    
		 int zu=sca.nextInt();		 
		 int limit=sca.nextInt();
		 int[][] map=new int[limit][2];
		 for(int i=0;i al = new ArrayList();
		//   ,     1,      
		if(fun1(0,zu,1,al,map)) {
			return true;
		}
		al.remove(0);
		if(fun1(0,zu,2,al,map)) {
			return true;
		}
		return false;
	}
	//fun1(    ,   ,        ,    ,      )
	static boolean fun1 (int index,int zu,int rl,ArrayList al,int[][] map) {
		boolean flag=false;
		if(index==zu) { //            ,      
			return true;
		}
		else {
			/*
			 *            ,            ,            ,    
			 *                ,             ,     
			 */
			al.add(index*2+rl);	
			if(fun2(al,map)) {	
				if(fun1(index+1,zu,1,al,map)) {
					return true;
				}
				if(fun1(index+1,zu,2,al,map)) {
					return true;
				}
			}
			else {
				
				al.remove(al.size()-1);
				return false;
			}
			
		}
		return flag;
	}
	//             ,     ,  true
	static boolean fun2(ArrayList al,int[][] map) {
		boolean flag=true;
		for (int i=0;i

 
 

좋은 웹페이지 즐겨찾기