여러분은 이웃한 나라인 A국으로 스파이를 파견했다. A국의 국회는 야당과 여당의 2당 체제인데, A국의 정치인들은 직선적이고 한번 뜻을 세우면 굽히지 않는 강직한 성격을 가지고 있다. 따라서 A국의 정치인들은 다음과 같은 원칙에 따라 편을 가른다.
A국에 파견된 첩보원은 자신이 알아낸 A국 정치인들 사이의 인간관계를 지속적으로 보고하고 있다.
그런데 당신은 요즘 이 첩보원이 적에게 포섭되어 배신한 것이 아닌지 의심하고 있다. 만일 그가 배신하여 잘못된 정보를 알려준다면 대 A국 전략을 수립하는 데에 어려움이 생길 것이다.
정치인인 동시에 유능한 프로그래머이자 장래가 촉망받는 치킨업 후계자인 여러분은 스파이가 거짓말을 하고 있는지를 검사해 보려고 한다.
입력 형식 첫 줄에 A국 정치인의 수 N(<=100000), 처리할 명령의 수 M(<=1000000)이 주어진다.
이후 M개의 줄에 대해서 다음 형식의 입력이 들어온다.
a b x : 첩보원이 a와 b가 친구 또는 적이라는 보고를 했음을 말한다. x가 'e'이면 두 정치인은 적이고, 'f'이면 두 정치인은 친구이다.
출력 형식 스파이의 보고 중에서 모순이 발생하는 첫 번째 보고의 번호를 출력한다. 입력의 마지막까지 모순이 발생하지 않았다면 "THE SPY DID NOT BETRAY"를 출력한다.
입력 예제
3 3
1 2 f
2 3 e
1 3 f
출력 예제
3
해설) 1과 2는 친구이고 2와 3이 적이므로 1과 3은 서로 적이어야 한다.
입력 예제
5 7
1 2 f
3 4 e
4 5 f
2 4 e
1 3 e
1 4 e
5 3 e
출력 예제
5
34개의 풀이가 있습니다.
예제 2번으로부터 간단한 아이디어를 설명하겠습니다. 먼저 생각할 수 있는 방법으로는 그래프를 생성하면서 DFS를 통해 a로부터 b로 가는 길이 있는지 검사하는 방법이 있죠. 그러나 이는 O(NM) 해법이고, N과 M이 너무 커지면 메모리도 많이 필요하고 시간도 오래 걸리게 됩니다.
다음으로 생각할 수 있는 방법은 한 점을 기준으로 하여, 이 점으로부터 다른 점들을 friend인지, enemy인지 관계를 배열에 저장하는 겁니다. 그러나 서로간에 어떤 관계인지 모르던 두 사람 사이에 대한 정보가 들어왔을 때, 기준점과 연결되어 있지 않았던 점들은 다시 순회하면서 값을 갱신해야 할 필요가 있습니다.
여기에서 더 나아가서 서로소 집합 자료구조를 이용하면 이 문제를 빠르게 해결할 수 있습니다.
최초에는 N개의 집합이 존재합니다. (1) (2) (3) (4) (5)
각 집합에는 대표가 되는 값이 있고, 이 대표와의 관계가 무엇인지를 기억하는 겁니다. 이는 집합을 합치는 시점에 O(1)로 계산이 가능합니다.
1 2 f -> (1, 2f) (3) (4) (5)
3 4 e -> (1, 2f) (3, 4e) (5)
4 5 f -> (1, 2f) (3, 4e, 5e)
2 4 e -> (1, 2f, 3f, 4e, 5e)
1 3 e -> 모순 발견
1 4 e
5 3 e
이때 두 집합이 합쳐질 때 결국 한쪽 집합을 순회하면서 관계를 갱신해줘야 하는 것 아니냐고요? 그렇지 않습니다. 각각의 집합을 트리 형태로 나타내고 대표값을 트리의 루트가 되도록 표현하는 겁니다. 어떤 사람이 집합 대표와 무슨 관계인지 알고 싶으면 부모를 따라서 루트에 도달하는 과정만을 추적하면 되는 거죠. 그럼 합치는 과정은 두 트리 루트 사이에 간선을 추가하는 것과 같죠.
Path compression 휴리스틱을 이용하면 서로소 집합을 구성하고 순회하는 전체 시간복잡도는 아몰타이즈드 1이 됩니다. 그래서 이 풀이의 전체 시간복잡도는 Max(n, m) 이겠죠.
class FriendOrEnemy
def initialize(size)
@parent = []
@relation = Array.new(size+1, 0)
1.upto(size) do |i|
@parent[i] = i
end
end
def rootOf(a)
nodes = []
mod = 0
root = a
while root != @parent[root]
nodes << root
mod ^= @relation[root]
root = @parent[root]
end
retval = [root, mod]
#path compression for speed
nodes.each do |e|
@parent[e] = root
mod, @relation[e] = mod ^ @relation[e], mod
end
retval
end
def friend?(a, b)
ra = rootOf(a)
rb = rootOf(b)
ra[0] == rb[0] and ra[1] ^ rb[1] == 0
end
def enemy?(a, b)
ra = rootOf(a)
rb = rootOf(b)
ra[0] == rb[0] and ra[1] ^ rb[1] != 0
end
def connect(a, b, fe)
ra = rootOf(a)
rb = rootOf(b)
if ra[0] != rb[0]
@parent[ra[0]] = rb[0]
@relation[ra[0]] = fe ^ ra[1] ^ rb[1]
end
end
end
def f_or_e(lines)
n, m = lines.first.split(" ").map(&:to_i)
ds = FriendOrEnemy.new(n)
index = 1
lines.drop(1).each do |line|
line =~ /(\d+)\s+(\d+)\s+([ef])/
a, b, ef = $1.to_i, $2.to_i, $3
if ef == 'e'
return index if ds.friend?(a, b)
ds.connect(a, b, 1)
#ds.print
elsif ef == 'f'
return index if ds.enemy?(a, b)
ds.connect(a, b, 0)
#ds.print
end
index += 1
end
return "THE SPY DID NOT BETRAY"
end
puts f_or_e (["3 3", "1 2 f", "2 3 e", "1 3 f"])
puts f_or_e (["5 7", "1 2 f", "3 4 e", "4 5 f", "2 4 e", "1 3 e", "1 4 e", "5 3 e"])
puts f_or_e (["5 7", "1 2 f", "3 4 e", "4 5 f", "2 4 e", "1 3 f", "1 4 e", "5 3 e"])
python 2.4 환경에서 풀이했습니다. 리스트를 이용한 배열을 이용해서 해결했습니다. 코드는... 윗분들 처럼 깔끔하지는 못한것 같네요~
def inputValue():
# 인원수와 명령수를 입력 받음
manCount, orderCount = raw_input('input :').split()
array = []
orderList = []
orderDict = {'f':1, 'e':-1} # f 는 1로 e는 -1 로 바꿔주기 위한 Dict
# 입력 받은 명령 수 만큼 데이터 입력을 받아줍니다
for num in range(int(orderCount)):
val1, val2, status = raw_input('>>').split()
orderList.append([int(val1), int(val2), orderDict[status]])
array = [int(manCount), orderList]
return array
def init_square(arg_num):
# 인원수사이즈의 정사각형 배열 생성
square = [[0 for col in range(arg_num)] for row in range(arg_num)]
return square
def inOrder(square, arg_order):
# 전달받은 명령어의 좌표와 반대좌표에 친구, 적 여부를 등록
square[arg_order[0]-1][arg_order[1]-1] = arg_order[2]
square[arg_order[1]-1][arg_order[0]-1] = arg_order[2]
def check_spy(square, val_x, val_y, state):
# 스파이 여부를 체크 (스파이가 체크 되면 False )
for row in range(len(square)):
# 본인 또는 상대 좌표의 경우 체크하지 아니하며, 상대 좌표의 상태가 0이 아닌 경우만 체크
if not((row == val_x) or (row == val_y)) and (square[val_y][row] != 0) :
# 체크 하는 본인좌표 및 상대좌표의 계산 값이 같은경우 또는 본인좌표 상태가 0인 경우에만 입력
if ((square[val_x][row] == square[val_y][row] * state) or square[val_x][row] == 0) :
square[val_x][row] = square[val_y][row] * state
else:
square[val_x][row] = 'X'
return False
return True
def main():
initList = inputValue()
manCount = initList[0]
square = init_square(manCount)
order = initList[1]
rtn = True
# 명령 순차 입력
for row in range(len(order)):
inOrder(square, order[row])
# manCount X manCount 좌표 순환 (check_spy의 상태가 false가 되면 종료)
for i in range(manCount):
for j in range(manCount):
if square[i][j] != 0 and rtn != False:
rtn = check_spy(square, i, j, square[i][j])
print "Order : [%d]" % int(row+1)
for l in range(len(square)):
print square[l]
if rtn == False:
print "Spy Order : %d " % int(row+1)
return
if __name__ == '__main__':
main()
코드내에 주석을 간단히 적어 놓았지만 추가로 설명을 붙이자면,
보시면서 개선했으면 하는 부분에 대해서 조언해주시면 많은 참고하겠습니다.
// SP_Spy.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//
#include "stdafx.h"
#include <string.h>
#define FRIEND (1)
#define ENERMY (-1)
bool InfomationVerify(char** p,int A,int B,char INFO,int size )
{
if(p[A][B] == 0 )
{
p[A][B] = INFO;
p[B][A] = INFO;
for(int iter = 1 ; iter <= size ; iter ++)
if(p[A][iter] != 0)
if(InfomationVerify(p,iter,B,p[A][iter]*INFO,size) == false)
return false;
}else
return p[A][B] == INFO ?true : false;
return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
while(1)
{
int N = 0,K=0;
printf("?");
scanf("%d %d",&N,&K);
if(N ==0 )
break;
char **p = new char*[N+1];
for(int iter = 0 ; iter <= N ;iter ++)
{
p[iter] = new char[N+1];
memset(p[iter],0,sizeof(char)*(N+1));
}
bool bFind = false;
int nLine = 0;
for(int iter = 0 ; iter < K; iter ++)
{
int A,B;
char R;
char INFO = 0;
scanf("%d %d %c",&A,&B,&R);
if(R == 'f')
INFO = 1;
else if( R == 'e')
INFO = -1;
if(A > N || B > N || INFO == 0)
{
iter --;
printf("Wrong Input Try Again!\n?");
continue;
}
if(InfomationVerify(p,A,B,INFO,N) == false)
{
bFind = true;
nLine = iter +1;
break;
}
}
if(bFind)
printf("%d\n",nLine);
else
printf("THE SPY DID NOT BETRAY\n");
}
return 0;
}
재귀로 풀었습니다.
bool InfomationVerify(char** p,int A,int B,char INFO,int size )
위 함수에 입력값을 넣어서 지금 들어온 정보를 가지고 전에 있는 정보를 검증 하고 생성 하는 구문입니다.
파이썬입니다.
# -*- coding: utf-8 -*-
import unittest
import traceback
import sys
class Person:
def __init__(self, name):
self.friends = []
self.enemies = []
self.name = name
def addFriend(self, person):
if person in self.enemies:
raise RuntimeError("%s is enemy" % person)
if person in self.friends: return
else: self.friends.append(person)
for f in self.friends: f.addFriend(person)
for e in self.enemies: e.addEnemy(person)
def addEnemy(self, person):
if person in self.friends:
raise RuntimeError("%s is friend" % person)
if person in self.enemies: return
else: self.enemies.append(person)
for f in self.friends: f.addEnemy(person)
for e in self.enemies: e.addFriend(person)
def __str__(self):
return self.name
def checkSpy(src):
src = src.strip()
lines = src.split("\n")
personCount, commandCount = lines[0].split()
persons = [Person(""+str(i+1)) for i in range(int(personCount))]
for no, line in enumerate(lines[1:]):
name1, name2, fe = line.split()
p1 = persons[int(name1)-1]
p2 = persons[int(name2)-1]
try:
if fe == 'f': p1.addFriend(p2)
elif fe == 'e': p1.addEnemy(p2)
except:
#traceback.print_exc(file=sys.stdout)
return str(no+1)
return "THE SPY DID NOT BETRAY"
class Test(unittest.TestCase):
def testSpy1(self):
src = """
3 3
1 2 f
2 3 e
1 3 f"""
self.assertEquals("3", checkSpy(src))
def testSpy2(self):
src = """
8 10
1 2 f
2 3 f
3 4 f
4 5 f
5 6 f
6 7 f
7 8 f
1 8 f
3 8 f
1 8 e
"""
self.assertEquals("10", checkSpy(src))
def testSpy3(self):
src = """
4 4
1 2 f
2 3 f
3 4 e
1 4 e
"""
self.assertEquals("THE SPY DID NOT BETRAY", checkSpy(src))
def testSpy4(self):
src = """
5 7
1 2 f
3 4 e
4 5 f
2 4 e
1 3 e
1 4 e
5 3 e
"""
self.assertEquals("5", checkSpy(src))
if __name__ == "__main__":
unittest.main()
적들과 친구들을 가진 Person 클래스를 생성하고 친구나 적을 추가시에 친구의 친구, 친구의 적, 적들의 적 또는 적들의 친구까지 재귀적으로 추가할 수 있게 하여 풀어보았습니다.
대량 검증케이스가 있을 경우 성능이 어떨지는 모르겠네용..
Java입니다. 수정했습니다. 수정이전 r값을 직접 출력하던 것을, 두 정치인의 관계를 나타내는 표시로 출력하는 것으로 수정했습니다
(초기값은 -1 →출력시 '.') 연관이 있는 두 정치인의 경우 그 값을 2로 나눈 값이 같게 됩니다.
f이면 같은 값을 (a,a),
e이면 2로 나눈 값은 같은데 차이가 1이 나는 값을 가지게 됩니다. (a,A) 예: (0,1), (2,3), (4,5), (6,7), ...
→int값이므로 2로 나눠도 소수점 이하 값은 버려지므로, 위 예의 쌍들은 나누기2한 값이 같습니다.
# 출력 예제 5 7
1 2 f (.,.) 1)0 2)0 3). 4). 5).
3 4 e (.,.) 1)0 2)0 3)2 4)3 5).
4 5 f (a,.) 1)0 2)0 3)2 4)3 5)3
2 4 e (a,b) 1)0 2)0 3)0 4)1 5)1
1 3 e (a,a)
5
* 정치인 배열 poli[N] ~초기화: 모든 값 -1 →출력시 '.' → 1). 2). 3). 4). 5).
poli[n]은 스파이의 보고에 따라 값을 가지는데, ← (보고형식) report[i][0] report[i][1] refr[i]
먼저 스파이의 보고를 두 정치인의 (연산 이전) 값에 따라 다섯가지 타입으로 나누어서 r에 저장했습니다
(r은 보고받은 두 정치인의 관계를 나타냅니다)
r= 0:(.,.) 1:(a,.) 2:(.,a) 3:(a,a) 4:(a,A) 5:(a,b) 초기값 (-1)→'.' (출력시)
r= 0 : (.,.) 보고받은 두 정치인 모두 값이 없는 상태(초기값 -1)일 경우,
(값 부여 단계)
다른 정치인들의 값과 겹치지 않게 '2로나눈 값(T)'이 다른(T++;) 새로운 값의 쌍을 주게 됩니다.
0:(.,.) → T++; → f : (T*2,T*2) 이거나, e : (T*2, T*2+1)
r=1,2 : 1:(a,.) 2:(.,a) 두 정치인 중 한쪽만 값을 가진 상태
(값 부여 단계)
f일 경우 → (a,a) 값이 있는 쪽 값을 값이 없던 쪽에 줍니다.
e일 경우 → (a,a±1) '2로 나눈 값(T)'이 같고 차이가 1인 값을 값이 없던 쪽에 줍니다.
r=3,4 : 3:(a,a) 4:(a,a±1) (3)서로 값이 같거나, (4)'2로 나눈 값(T)'이 같고 차이가 1인 상태
(모순 검사 단계)
ex) 1 4 e (a,A) 1)0 2)0 3)0 4)1 5)1 → 모순 없음.
여기서 f일 경우 r=3 (a,a), e일 경우 r=4 (a, a±1)이면 보고가 맞는 것인데,
그렇지 않을 경우 모순이 발생하므로 → 이 단계에서 연산을 종료하고 이 보고번호(i+1)를 출력합니다.
r= 5 : (a,b) 두 값이 서로 상관없던 값일 경우. 즉, '2로 나눈 값(T)'이 다른 경우
(값 변환 단계)
ex)
4 5 f (a,.) 1)0 2)0 3)2 4)3 5)3 (r=1, 이전꺼)
2 4 e (a,b) 1)0 2)0 3)0 4)1 5)1 (r=5, 요기에서)
ex에서 2번 4번 정치인의 값은 (0,3)이었고, 0→T=0/2=0, 3→T=3/2=1로 T가 달라서 ⇒ r=5
이 둘은 e(적)이라는 보고가 올라왔으므로,
두 값 중 적은 쪽 값에 맞추어 다른 하나의 값을 '2로 나눈 값(T)'이 같은 값, 그러나 차이가 1인 값으로 변환합니다.
(ex에서) (0,3) → e : (0,1), 즉 3 → 1
또한, poli[N]배열 전체에서, 바뀌기 전 값이었던 3과 T가 같은 값 (T=1)(2,3)모두를 (T=0)(0,1)쌍으로 변환합니다
(ex에서) e이므로, 3 → 1 & 2 → 0
만약 f였다면, 반대로 (0,3) → f : (0,0)가 되어 3 → 0 & 2 → 1 으로 변환했겠죠.
poli[N]배열 전체에서, f,e에 따라서, 바뀌게 되는 값과 T가 같은 값(T=1)(2, 3) 모두를,
바꿀 값과 같은 T를 가진 값(T=0)(0, 1)으로 변환합니다.
#출력 예제 3 3
1 2 f (.,.) 1)0 2)0 3).
2 3 e (a,.) 1)0 2)0 3)1
1 3 f (a,A)
3
#출력예제 5 6
1 2 f (.,.) 1)0 2)0 3). 4). 5).
3 4 e (.,.) 1)0 2)0 3)2 4)3 5).
4 5 f (a,.) 1)0 2)0 3)2 4)3 5)3
2 4 e (a,b) 1)0 2)0 3)0 4)1 5)1
1 4 e (a,A) 1)0 2)0 3)0 4)1 5)1
1 5 e (a,A) 1)0 2)0 3)0 4)1 5)1
THE SPY DID NOT BETRAY.
코드 중 /*과정출력1*/ /*과정출력2*/ 부분을 삭제하셔야 문제에서 요구했던 대로 출력합니다.
제 설명에 있는 대로 과정이 출력되게 하려면 저 부분을 그대로 두시면 됩니다.
package h_friend_or_spy;
public class Relation {
int relate(int[] p, int[] re, String[] rP){
//r= 0:(.,.) 1:(a,.) 2:(.,a) 3:(a,a) 4:(a,A) 5:(a,b) 초기값'.': -1
int r1=p[re[0]-1], r2=p[re[1]-1];
if(r1<0&&r2<0){ rP[0]=".,."; return 0;}
else if(r1>=0&&r2<0){ rP[0]="a,."; return 1;}
else if(r1<0&&r2>=0){ rP[0]=".,a"; return 2;}
else if(r1>=0&&r2>=0){
if(r1==r2){ rP[0]="a,a"; return 3;}
else if( (r1/2)==(r2/2) ){ rP[0]="a,A"; return 4;}
else{ rP[0]="a,b"; return 5;}
} else { rP[0]="def"; return 6;} //(6이 리턴될 리가 없음)
}
}
package h_friend_or_spy;
import java.util.Scanner;
public class Spy {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
Relation R=new Relation();
int i,j, T=-1, r, r1,r2, a1,a2,b1,b2,t1,t2;
String[] rP=new String[1];
int N=in.nextInt(), M=in.nextInt();
int[] poli=new int[N];
for(i=0;i<N;i++) poli[i]=-1; //처음엔 poli배열을 -1값으로 초기화 :'.'로 출력
int[][] report=new int[M][2];
boolean[] refr=new boolean[M]; //f:true, e(혹은 그외 문자):false
for(i=0;i<M;i++){ //보고입력받음
report[i][0]=in.nextInt();
report[i][1]=in.nextInt();
refr[i]=false;//초기화값 → 'f'를 입력받지 않으면 모두 'e'(false)로 처리
if(in.next().charAt(0)=='f') refr[i]=true;
}
Check:
for(i=0;i<M;i++){
r1=report[i][0]-1; r2=report[i][1]-1;
r=R.relate(poli, report[i], rP);
/*과정출력1*/
System.out.print(report[i][0]+" ");
System.out.print(report[i][1]+" ");
System.out.print( ((refr[i])?'f':'e')+" ");
System.out.print("("+rP[0]+") ");
/*과정출력1 end*/
//r= 0:(.,.) 1:(a,.) 2:(.,a) 3:(a,a) 4:(a,A) 5:(a,b) 초기값'.': -1
switch(r){
case 0:
T++;
poli[r1]=T*2;
if(refr[i]) poli[r2]=T*2;
else poli[r2]=T*2+1;
break;
case 1:
if(refr[i]) poli[r2]=poli[r1];
else poli[r2]= (poli[r1]%2==0)? poli[r1]+1:poli[r1]-1;
break;
case 2:
if(refr[i]) poli[r1]=poli[r2];
else poli[r1]= (poli[r2]%2==0)? poli[r2]+1:poli[r2]-1;
break;
case 3:
if(refr[i]) break;
else break Check;
case 4:
if(refr[i]) break Check;
else break;
case 5:
a1= (poli[r1]<poli[r2])? poli[r1]:poli[r2]; //b를 a로 만듦(a가 작은 수)
a2=(a1%2==0)?a1+1:a1-1;
t1= (poli[r1]<poli[r2])? poli[r2]:poli[r1];
t2=(t1%2==0)?t1+1:t1-1;
if(refr[i]){ b1=t1; b2=t2; }
else{ b1=t2; b2=t1; }
for(j=0;j<N;j++){
if(poli[j]==b1) poli[j]=a1;
if(poli[j]==b2) poli[j]=a2;
}
break;
}
/*과정출력2*/
for(j=0;j<N;j++){
System.out.print((j+1)+")");
if(poli[j]==-1) System.out.print(". ");
else System.out.print(poli[j]+" ");
} System.out.println();
/*과정출력2 end*/
}
if(i==M) System.out.println("THE SPY DID NOT BETRAY.");
else System.out.println("\n"+(i+1));
}
}
혹은, 이렇게 두 정치인의 연산이전 관계를 나타내는 r표시를
직접 연산 이전 두 정치인의 관계 값으로 나타내려면, 아래의 Relation함수를 쓸 수 있습니다
#출력예제 5 6
1 2 f (.,.) 1)0 2)0 3). 4). 5).
3 4 e (.,.) 1)0 2)0 3)2 4)3 5).
4 5 f (3,.) 1)0 2)0 3)2 4)3 5)3
2 4 e (0,3) 1)0 2)0 3)0 4)1 5)1
1 4 e (0,1) 1)0 2)0 3)0 4)1 5)1
1 5 e (0,1) 1)0 2)0 3)0 4)1 5)1
THE SPY DID NOT BETRAY.
package h_friend_or_spy;
public class Relation {
int relate(int[] p, int[] re, String[] rP){
//r= 0:(.,.) 1:(a,.) 2:(.,a) 3:(a,a) 4:(a,A) 5:(a,b) 초기값'.': -1
int r1=p[re[0]-1], r2=p[re[1]-1];
rP[0]=((r1==-1)?".":r1)+","+((r2==-1)?".":r2);
if(r1<0&&r2<0) return 0;
else if(r1>=0&&r2<0) return 1;
else if(r1<0&&r2>=0) return 2;
else if(r1>=0&&r2>=0){
if(r1==r2) return 3;
else if( (r1/2)==(r2/2) ) return 4;
else return 5;
} else return 6; //(6이 리턴될 리가 없음)
}
}
Kim Jaeju님의 방법에 따라 C++로 작성해보았습니다. XCode 5.1.1에서 작성되었습니다.
//
// main.cpp
// CodingDojang-420-CCP
//
// Created by Chrome-MBPR on 7/3/14.
// Copyright (c) 2014 cr2025x1. All rights reserved.
//
#include <iostream>
#include <list>
#include <cassert>
using namespace std;
class ffi_node;
class ffi_junc;
struct node_and_ffi {
ffi_node* node;
bool ffi;
};
typedef struct node_and_ffi node_and_ffi;
// Node's "junction" to its subnodes.
class ffi_junc : public list<ffi_node*> {
protected:
bool _ffi; // 0 = enemy, 1 = friend
ffi_node* _parent;
public:
bool ffi(void) const {return _ffi;}
void set_ffi(bool ffi) {_ffi = ffi;}
ffi_node* parent(void) const {return _parent;}
void set_parent(ffi_node* parent) {_parent = parent;}
};
// Node for each persons.
class ffi_node {
protected:
ffi_junc _junc[2];
ffi_junc* _parent; // NULL if this node is the root.
public:
ffi_node() {
_junc[0].set_ffi(0);
_junc[0].set_parent(this);
_junc[1].set_ffi(1);
_junc[1].set_parent(this);
_parent = NULL;
}
ffi_junc* junc(unsigned int i) {assert(i <= 1); return &_junc[i];}
ffi_junc* set_junc(unsigned int i) {assert(i <= 1); return &_junc[i];}
ffi_junc* parent(void) const {return _parent;}
void set_parent(ffi_junc* parent) {_parent = parent;}
// Finds the root of the tree that this node belongs and this node's FFI to the root.
node_and_ffi root_and_ffi(void) {
node_and_ffi result;
ffi_junc* parent_junc = _parent;
ffi_node* parent_node = NULL;
bool ffi = 1;
if (parent_junc == NULL) {
result.node = this;
result.ffi = ffi;
return result;
}
else {
do {
ffi = parent_junc->ffi() == ffi;
parent_node = parent_junc->parent();
parent_junc = parent_node->parent();
} while (parent_junc != NULL);
}
result.node = parent_node;
result.ffi = ffi; // This node's Friendy-or-Foe Information to the root node.
return result;
}
};
int main(int argc, const char * argv[])
{
const unsigned int number_of_relation_set = 7;
const unsigned int number_of_persons = 5;
unsigned int relationArray[number_of_relation_set][3] = { {1, 2, 1}, {3, 4, 0}, {4, 5, 1}, {2, 4, 0}, {1, 3, 0}, {1, 4, 0}, {5, 3, 0} }; // 2nd index 0 and 1 = person, 2 = friendly or foe
ffi_node person[number_of_persons + 1]; // Element at index 0 will not be used in this example.
for (unsigned int i = 0; i < number_of_relation_set; i++) {
node_and_ffi root_of_second = person[relationArray[i][1]].root_and_ffi();
node_and_ffi root_of_first = person[relationArray[i][0]].root_and_ffi();
if (root_of_first.node == root_of_second.node) {
// Both nodes are in the same tree
if (root_of_first.ffi != root_of_second.ffi == relationArray[i][2]) {
// Known Friendly-or-Foe Identification of two person and its given FFI is inconsistant.
cout << i + 1 << endl;
return 0;
}
continue;
}
else {
bool ffi = relationArray[i][2] == root_of_second.ffi;
root_of_first.node->set_junc(ffi)->push_back(root_of_second.node);
root_of_second.node->set_parent(root_of_first.node->junc(ffi));
}
}
// All given FoF info is consistant.
cout << "THE SPY DID NOT BETRAY" << endl;
return 0;
}
저도 한번 풀어봤습니다. 좀 단순히 생각해서, 정치가 리스트를 만들어놓고 사용자의 입력이 주어질때마다 입력된 두 정치가 사이의 사이를 기록하는 방식을 사용하였습니다. 단, 입력 중 이전까지 입력된 정치가들과는 아무런 관계가없는 정치가들이 입력될 경우 관계 번호(일련번호)를 별도로 할당하고 도잇에 둘 사이의 관계(적/아)를 기록하였습니다. 그리고 이제까지는 관계를 모르던 두 그룹간의 합병시에는 두 그룹의 관계번호를 합쳤습니다. 다만, 여기서 문제가되는 지금까지 기록된 다른 두 그룹속의 정치가들의 적/아 번호를 통일하는 문제가 생기는데 이는 관계 객체내 적/아 구분을 간접 참조하도록 하여 정치가 객체내 rawSideNum이 참조하고 있는 번호를 sideNum으로 변경하여 적/아를 구분할 수 있도록 하여 해결하였습니다. 코드는 Python 3.3.2에서 작성되었습니다.
# spytest.py
class Relation:
def __init__(self, relationNum):
self.relationNum = relationNum
def chageSides():
sides[0],sides[1] = sides[1],sides[0]
sides = [0,1]
class Politician:
def __init__(self, relation):
self.relation = relation
self.rawSideNum = 0
def getSideNum(self):
return self.relation.sides[self.rawSideNum]
def getRelationNum(self):
return self.relation.relationNum
def getFriend(self):
ret = Politician(self.relation)
ret.rawSideNum = self.rawSideNum
return ret
def getEnemy(self):
ret = Politician(self.relation)
ret.rawSideNum = 1-self.rawSideNum
return ret
def setFriend(self, politician):
politician.relation.relationNum = self.relation.relationNum
if self.getSideNum() != politician.getSideNum():
politician.relation.changeSides()
def setEnemy(self, politician):
politician.relation.relationNum = self.relation.relationNum
if self.getSideNum() == politician.getSideNum():
politician.relation.changeSides()
def spyTest(pNum, qNum, qList):
rNum = 0
pList = [None]*(pNum)
for i in range(qNum):
p0, p1, r = qList[i]
p0, p1 = p0-1, p1-1
# 입력된 두 정치가 모두 지금까지 입력된적 없는 정치가일경우
if not pList[p0] and not pList[p1]:
# 첫번째 정치가를 생성하고, 나머지 정치가를 해당 정치가의 friend또는 enemy로 만든다
pList[p0] = Politician(Relation(rNum));rNum+=1
pList[p1] = pList[p0].getFriend() if r=='f' else pList[p0].getEnemy()
# 입력된 두 정치가 모두가 이전에 입력된 정치가일때
elif pList[p0] and pList[p1]:
# 두 정치가의 관계번호가 동일할 때에만 오류 판단이 가능
if pList[p0].getRelationNum() == pList[p1].getRelationNum():
if (pList[p0].getSideNum() == pList[p1].getSideNum() and r == 'e') or (pList[p0].getSideNum() != pList[p1].getSideNum() and r == 'f'):
return i+1
# 두 정치가의 관계번호가 다르다면, 해당 관계들의 합병을 해야함
else:
if r=='f':
pList[p0].setFriend(pList[p1])
else:
pList[p0].setEnemy(pList[p1])
else:
# 둘 중하나만 이전에 입력된 정치가라면
if pList[p1]: p0, p1 = p1, p0
# 기 입력된 정치가를 기분으로 적/아를 구분하여 정치가 객체 생성
pList[p1] = pList[p0].getFriend() if r=='f' else pList[p0].getEnemy()
# 모든 루프가 정상 종료될경우 0을 반환하여 스파이가 아님을 표시
return 0
def printResult(ret):
if ret == 0:
print("THE SPY DID NOT BETRAY")
else:
print(ret)
def main():
pNum = 3
qNum = 3
qList = [[1,2,'f'],[2,3,'e'],[1,3,'f']]
ret = spyTest(pNum, qNum, qList)
assert(ret==3)
printResult(ret)
pNum = 8
qNum = 10
qList = [[1,2,'f'],[2,3,'f'],[3,4,'f'],[4,5,'f'],[5,6,'f'],[6,7,'f'],[7,8,'f'],[1,8,'f'],[3,8,'f'],[1,8,'e']]
ret = spyTest(pNum, qNum, qList)
assert(ret==10)
printResult(ret)
pNum = 4
qNum = 4
qList = [[1,2,'f'],[2,3,'f'],[3,4,'e'],[1,4,'e']]
ret = spyTest(pNum, qNum, qList)
assert(ret==0)
printResult(ret)
pNum = 5
qNum = 7
qList = [[1,2,'f'],[3,4,'e'],[4,5,'f'],[2,4,'e'],[1,3,'e'],[1,4,'e'],[5,3,'e']]
ret = spyTest(pNum, qNum, qList)
assert(ret==5)
printResult(ret)
if __name__=='__main__':
main()
메모리를 먹는 방법인지 알지만 이 문제는 마치 transitive closure를 구하는 것 같아서 이를 구하는 Floyd–Warshall 알고리즘처럼 구해봤습니다. 쉽게 설명하면, (i, j) 사이의 관계가 알려져있다면, (i, k)과 (k, j), (k != i and k != j)의 관계와 비교해서 모순이 있는지 살펴봅니다. 만약, (i, j) 관계가 아직 없다면 (i, k), (k, j) 관계로부터 추이 관계를 갱신합니다. 뭐, 여전히 메모리를 O(n^3)로 먹긴 하지만 정치인 관계가 교환적이므로 upper triangle 행렬만 만들어 쓰면 됩니다. 관계는 친구와 적을 1, -1로 하면 곱하기로 추이 관계를 쉽게 얻을 수 있습니다. 다른 분이 하신 것도 결과적으론 다 비슷한 것 같습니다. 제가 너무 Floyd-Warshall 알고리즘에 얽매여 푼 것 같기도 합니다.
그나저나 아주 좋은 문제입니다.
#include <iostream>
#include <vector>
#include <tuple>
#include <cassert>
#include <algorithm>
// Rules:
// Friend -> Friend = Friend
// Friend -> Enemy = Enemy
// Enemy -> Friend = Enemy
// Enemy -> Enemy = Friend
// So, we can use -1, 1 and multiplication to compute transitive relations.
enum relation {
kEnemy = -1,
kFriend = 1,
kUnknown = 0,
};
int process(int n, const std::vector<std::tuple<int, int, relation>> reports) {
using namespace std;
// As the relationships of given two politicians are symmetric, create only an
// upper n x n matrix. M stores the relationship of p1 and p2, where p1 < p2.
//
// Examples of 5 politicians:
// (p1 = 1, p2 = 2, f) is stored at M[0][0].
// (p1 = 5, p2 = 3, e) is stored at M[2][1], after swapping p1 and p2.
//
// 1 2 3 4 5
// 1 . f * * *
// 2 . . * * *
// 3 . . . * e
// 4 . . . . *
// 5 . . . . .
//
vector<vector<relation>> M;
for (int i = 0; i < n - 1; ++i) {
M.push_back({});
for (int j = i; j < n - 1; ++j) {
M[i].push_back(kUnknown);
}
}
// Note: p1 and p2 are the units of politician indices: [1, n] and p1 < p2.
auto setRelation = [&](int p1, int p2, relation rel) {
if (p1 > p2)
swap(p1, p2);
M[p1 - 1][p2 - p1 - 1] = rel;
};
auto getRelation = [&](int p1, int p2)->relation {
if (p1 > p2)
swap(p1, p2);
return M[p1 - 1][p2 - p1 - 1];
};
// Perform like Floyd–Warshall algorithm, that is compute transitive closure.
// If a relationship is already known, check the state is coherent.
auto updateAndVerify = [&]() -> bool {
for (int i = 1; i <= n - 1; ++i) {
for (int j = i + 1; j <= n; ++j) {
for (int k = i + 1; k <= n; ++k) {
if (k == j)
continue;
if (getRelation(i, j) != kUnknown) {
int transitive = getRelation(i, k) * getRelation(k, j);
if (transitive != kUnknown && getRelation(i, j) != transitive)
return false;
} else {
// Compute the transitive relationship.
setRelation(i, j, static_cast<relation>(getRelation(i, k) *
getRelation(k, j)));
}
}
}
}
return true;
};
for (size_t i = 0; i < reports.size(); ++i) {
int p1 = get<0>(reports[i]);
int p2 = get<1>(reports[i]);
assert(p1 != p2);
relation rel = get<2>(reports[i]);
setRelation(p1, p2, rel);
if (updateAndVerify() == false) {
cout << i + 1 << endl;
return i + 1;
}
}
cout << "THE SPY DID NOT BETRAY" << endl;
return 0;
}
int main() {
using std::make_tuple;
const relation f = kFriend;
const relation e = kEnemy;
int ret;
ret = process(3, {make_tuple(1, 2, f),
make_tuple(2, 3, e),
make_tuple(1, 3, f)});
assert(ret == 3);
ret = process(5, {make_tuple(1, 2, f),
make_tuple(3, 4, e),
make_tuple(4, 5, f),
make_tuple(2, 4, e),
make_tuple(1, 3, e),
make_tuple(1, 4, e),
make_tuple(5, 3, e)});
assert(ret == 5);
ret = process(8, {make_tuple(1, 2, f),
make_tuple(2, 3, f),
make_tuple(3, 4, f),
make_tuple(4, 5, f),
make_tuple(5, 6, f),
make_tuple(6, 7, f),
make_tuple(7, 8, f),
make_tuple(1, 8, f),
make_tuple(3, 8, f),
make_tuple(1, 8, e)});
assert(ret == 10);
ret = process(4, {make_tuple(1, 2, f),
make_tuple(2, 3, f),
make_tuple(3, 4, e),
make_tuple(1, 4, e)});
assert(ret == 0);
return 0;
}
본문의 내용중
나의 친구의 친구는 나의 친구이다
나의 친구의 적은 나의 적이다
나의 적의 친구는 나의 적이다
나의 적의 적은 나의 친구이다
친구를 0, 적을 1 로 놓았을때
0 @ 0 = 0
0 @ 1 = 1
1 @ 0 = 1
1 @ 1 = 0 과 같이 XOR 관계에 놓이게 됩니다. (친구를 1, 적을 0 으로 놓았을 경우엔 XNOR)
(결론적으로 X의 친구는 X, X의 적은 ~X, (단 X는 친구 혹은 적 둘중 하나여야함.)
문제를 풀기위해 주어진 정치인의 수 N 에 대한 1차원 배열을 만든후에 입력 명령에 따라서 배열을 룩업해서 두 요소가 모두 다 비어있을땐 적절한 초기값으로 채워주고(예를들면 1 2 f 의 경우엔 1의 위치에 초기값 true 를 넣어주고 1과 2의 관계가 f이므로 2에도 true를 채워주며 만약 관계가 e일 경우엔 1에 true를 2엔 false를 채워줌.) 둘중 하나가 비워져 있을땐 둘의 관계에 따라 적절한 나머지 값을 채워줍니다. 이러한 방법으로 값을 채워나가다가 이미 모두 채워져 있는 값들에 대한 비교가 나타날때 모순이 발생하면 명령의 번호를 출력한후 끝나며 끝까지 진행될 경우에 성공 메시지를 출력하면 될듯합니다.
이런 관계를 바탕으로 두번째 예제를 풀어보면
5 7
1 2 f
3 4 e
4 5 f
2 4 e
1 3 e
1 4 e
5 3 e
table| 1 | 2 | 3 | 4 | 5 |
1 2 f 의 경우 아직 1과 2에 대한 정보가 없기 때문에 1의 초기값을 true로, 2와의 관계가 f이기 때문에 2도 true로 대입함.
table| 1 | 2 | 3 | 4 | 5 |
..........| T | T |
3 4 e 의 경우 아직 3과 4에 대한 정보가 없기 때문에 3의 초기값을 true로, 4와의 관계가 e이기 때문에 4는 false로 대입함.
table| 1 | 2 | 3 | 4 | 5 |
..........| T | T | T | F |
4 5 f 의 경우 5에 대한 정보가 없기 때문에 4의 값과 f의 관계를 이용하여 false를 대입함.
table| 1 | 2 | 3 | 4 | 5 |
..........| T | T | T | F | F |
2 4 e 의 경우 2 와 4 모두 값이 들어있기 때문에 2와 4가 e의 관계를 만족하는지 확인해봄. ( 2(T), 4(F) 는 enemy 관계를 만족함.)
1 3 e 의 경우 1 과 3 모두 값이 들어있기 때문에 1과 3이 e의 관계를 만족하는지 확인해봄. ( 1(T), 3(T) 는 enemy 관계를 만족시키지 못함.)
따라서 [1 3 e] 다섯번째 명령에서 모순발생으로 5를 출력하고 프로그램 종료.
============================================================================
이런 방식으로 문제를 풀어봤는데요. 혹시 잘못된 점이 있는지 알려주시면 감사하겠습니다. (마크다운 문법으로 글을 작성하라고 쓰여져 있었는데 읽어봐도 무슨말인지 잘 모르겠네요...)
관계의 모순만 구해내면 되는 문제이므로, 집합간의 관계만 따져 친구끼리 합치는 컨셉으로 구현했습니다.
#include <stdio.h>
#include <set>
#include <map>
typedef std::set<int> member_t;
typedef struct Party {
int id;
int enemy;
member_t member;
} Party;
typedef std::map<int, Party> party_t;
typedef std::map<int, int> lookup_t;
int g_NextParty = 0;
party_t g_Party;
lookup_t g_Lookup;
Party& GetParty(int mem) {
lookup_t::const_iterator i = g_Lookup.find(mem);
if(i != g_Lookup.end())
return g_Party[i->second];
int id = g_NextParty++;
Party &p = g_Party[id];
p.id = id;
p.enemy = -1;
p.member.insert(mem);
g_Lookup[mem] = id;
return p;
}
bool Merge(Party &p1, Party &p2) {
if(p1.enemy == p2.id) return false;
if(p1.id == p2.id) return false;
p1.member.insert(p2.member.begin(), p2.member.end());
member_t::iterator i = p2.member.begin();
while(i != p2.member.end())
g_Lookup[*i++] = p1.id;
g_Party.erase(p2.id);
return true;
}
bool Friend(Party &p1, Party &p2) {
if(p1.id == p2.id) return true;
int e2 = p2.enemy;
if(!Merge(p1, p2)) return false;
if(e2 < 0) return true;
Party &e = g_Party[e2];
e.enemy = -1;
if(p1.enemy >= 0)
return Friend(g_Party[p1.enemy], e);
p1.enemy = e.id;
return true;
}
bool Enemy(Party &p1, Party &p2) {
if(p1.id == p2.id) return false;
if(p1.id == p2.enemy) return true;
if(p1.enemy != -1)
return Friend(p2, g_Party[p1.enemy]);
if(p2.enemy != -1)
return Friend(p1, g_Party[p2.enemy]);
p1.enemy = p2.id;
p2.enemy = p1.id;
return true;
}
bool AddRelation(int mem1, int mem2, bool is_friend) {
Party &p1 = GetParty(mem1), &p2 = GetParty(mem2);
bool ret = true;
if(is_friend)
ret = Friend(p1, p2);
else
ret = Enemy(p1, p2);
return ret;
}
int main(void) {
int n, m;
if(scanf_s("%u %u", &n, &m) != 2) {
printf("invalid input\n");
return 0;
}
for(int i = 0; i < m; i++) {
int a, b;
char x;
if(scanf_s("%d %d %c", &a, &b, &x) != 3) {
printf("invalid tuple\n");
return 0;
}
if(!AddRelation(a, b, x == 'f')) {
printf("%d", i+1);
return 0;
}
}
printf("THE SPY DID NOT BETRAY");
return 0;
}
아 다른 분들 코드가 왜이리 길지...하고 짜봤는데 제 코드가 더 기네요 -_-; 엉성하기 짝이 없지만 일단 올리고 수정해야겠어요.
class member :
def __init__(self, number) :
self.number = number
self.friend = []
self.enemy = []
f = open('spy.text','r')
m.n = f.readline().split()
aa = []
for i in range(int(m)):
new_m = member(i+1)
aa.append(new_m)
idx = 0
for in in range(int(n)):
a,b,ef = f.readline().split()
idx += 1
if ef == "f":
for me in aa[int(a)-1].friend:
aa[int(me)-1].friend.append(b)
for me in aa[int(a)-1].enemy:
aa[int(me)-1].enemy.append(b)
for me in aa[int(b)-1].friend:
aa[int(me)-1].friend.append(a)
for me in aa[int(b)-1].enemy:
aa[int(me)-1].enemy.append(a)
aa[int(a)-1].friend.append(b)
aa[int(b)-1].friend.append(a)
if ef == "e":
for me in aa[int(a)-1].friend:
aa[int(me)-1].enemy.append(b)
for me in aa[int(a)-1].enemy:
aa[int(me)-1].friend.append(b)
for me in aa[int(b)-1].friend:
aa[int(me)-1].enemy.append(a)
for me in aa[int(b)-1].enemy:
aa[int(me)-1].friend.append(a)
aa[int(a)-1].enemy.append(b)
aa[int(b)-1].enemy.append(a)
for me in aa :
for mee in me.enemy:
if mee in me.friend :
print idx
quit()
print "THE SPY DID NOT BETRAY"
using System.Collections.Generic;
using System.Linq;
public class Spy
{
public List<int> Outputs { get; set; }
public bool IsFriend { get; set; }
public Spy(List<int> outputs, bool isFriend)
{
Outputs = outputs;
IsFriend = isFriend;
}
}
public int FindSpy(List<string> inputs)
{
var spies = new List<Spy>();
for (int i = 0; i < inputs.Count; i++)
{
var split = inputs[i].Split(' ').ToList();
var x = int.Parse(split[0]);
var y = int.Parse(split[1]);
var isFriend = split.Last() == "f";
if (spies.Any(s => s.Outputs.Contains(x) || s.Outputs.Contains(y)))
{
var curr = spies.FirstOrDefault(s => s.Outputs.Contains(x) && s.Outputs.Contains(y));
if (curr != null)
{
if (curr.IsFriend != isFriend) return i + 1;
continue;
}
var temps = spies.Where(s => s.Outputs.Contains(x) || s.Outputs.Contains(y)).ToList();
for (int j = 0; j < temps.Count; j++)
{
var a = temps[j].Outputs.First(o => o != x && o != y);
var b = temps[j].Outputs.First(o => o == x || o == y) != x ? x : y;
foreach (var spy in spies)
if (spy.Outputs.Contains(a) && spy.Outputs.Contains(b) && spy.IsFriend != isFriend)
return i + 1;
spies.Add(new Spy(new List<int> { a, b }, isFriend));
}
continue;
}
spies.Add(new Spy(new List<int> { x, y }, isFriend));
}
return 0;
}
어렵네요.. 객체로 구성해서 각 노드간 친구냐 적이냐를 재귀적으로 모두 연결시키고, 새로운 명령어를 입력받을때 마다 모순을 검사하고 모순이 있으면 빠져나오게 했습니다.
pn, cn = map(eval,raw_input().split())
class Pol(object):
def __init__(self,name):
self.__name__ = name
self.f_list=[]
self.e_list=[]
def __repr__(self):
return self.__name__
def add_f(self,f):
if self.has_e(f): return "Error"
if f == self :return
self.f_list.append(f)
i=0
while i<len(f.f_list):
p=f.f_list[i]
if not self.has_f(p):self.add_f(p)
i+=1
i=0
while i<len(f.e_list):
p=f.e_list[i]
if not self.has_e(p):self.add_e(p)
i+=1
if not f.has_f(self) : return f.add_f(self)
def add_e(self,e):
if self.has_f(e) :return "Error"
if e == self:return
if self.has_e(e):return
self.e_list.append(e)
i=0
while i<len(e.f_list):
p=e.f_list[i]
if not self.has_e(p):p.add_e(self)
i+=1
i=0
while i<len(e.e_list):
p=e.e_list[i]
if not self.has_f(p):p.add_f(self)
i+=1
if not e.has_e(self) :return e.add_e(self)
def has_f(self,f):
if f in self.f_list : return True
else : return False
def has_e(self,e):
if e in self.e_list : return True
else : return False
p_list = [Pol(str(i)) for i in range(pn+1)]
commands = []
for i in range(cn):
commands.append(raw_input())
betray = False
for i,c in enumerate(commands):
a,b,r = c.split();a = int(a);b=int(b)
if r=='e':
if p_list[a].add_e(p_list[b]) == 'Error' :
betray = True
print i+1
break
if r=='f':
if p_list[a].add_f(p_list[b]) == 'Error' :
betray = True
print i+1
break
if not betray : print "THE SPY DID NOT BETRAY"
Python 2.7
Disjoint set 자료구조를 사용했습니다. 이 자료구조에 대한 설명은 Kim Jaeju님의 풀이를 참조하시면 되겠습니다.
1부터 n까지와 -n부터 -1까지의 값을 만들어, A와 B가 친구일 경우 A와 B를 합치고 -A와 -B를 합치게 했습니다. (물론 적일 경우 A와 -B, -A와 B를 합칩니다) Disjoint set의 시간 복잡도는 O(α(n))인데, 여기서 α는 Ackermann 함수 A(x,x)의 역함수로 실제 사용 가능한 범위에서는 사실상 상수입니다. 따라서 전체 시간복잡도는 O(m+nα(m))으로 볼 수 있습니다.
class Node:
def __init__(self, parent=None, value=0):
if parent == None:
self.parent = self
else:
self.parent = parent
self.value = value
self.rank = 0
class DSF:
def __init__(self, n):
self.n = n
self.nodes = [Node(value=i) for i in xrange(1,n+1)]\
+[Node(value=i) for i in xrange(-n,0)]
def find(self, x):
if type(x) == int:
x = self.nodes[x]
if x.parent != x:
x.parent = self.find(x.parent)
return x.parent
def union(self, x, y):
if type(x) == int:
x = self.nodes[x]
y = self.nodes[y]
xroot = self.find(x)
yroot = self.find(y)
if xroot == yroot:
return
if xroot.rank < yroot.rank:
xroot.parent = yroot
elif xroot.rank > yroot.rank:
yroot.parent = xroot
else:
yroot.parent = xroot
xroot.rank+= 1
########################
n, m = map(int, raw_input().split())
dsf = DSF(n)
info = [raw_input().split() for i in xrange(m)]
index = 1
betrayed = False
for i in info:
a, b, r = int(i[0]), int(i[1]), i[2]
if r == 'f':
if dsf.find(a) == dsf.find(-b):
print index
betrayed = True
break
dsf.union(a,b)
dsf.union(-a,-b)
elif dsf.find(a) == dsf.find(b):
print index
betrayed = True
break
dsf.union(a,-b)
dsf.union(-a,b)
index+= 1
if not betrayed:
print 'THE SPY DID NOT BETRAY'
Ruby
{노드ID: {루트:노드ID, 관계:적또는친구}}로 표현. 최상위 root 연결로 병합처리
모순정보를 찾는 xor연산의 편의성 목적으로 친구는 0, 적은 1로 치환.
root = ->n,nodes { n = nodes[n][:root] until nodes[n][:root]==n; n }
set_node = ->n,r,rel,nodes { nodes[n][:root]=r; nodes[n][:rel]=rel; nodes }
chk_cons = ->n, rel_info, nodes, incons do
a, b, rel = rel_info[n]
a_rel, b_rel = nodes[a][:rel], nodes[b][:rel]
# root가 동일할 때 모순체크, 그렇지 않으면 노드 연결
if root[a,nodes] == root[b,nodes]
incons << n if (a_rel||0)^(b_rel||0) != rel
else
nodes = case [a_rel.nil?, b_rel.nil?]
when [true, true] then set_node[b, a, rel, nodes]
when [false, true] then set_node[b, root[a,nodes], a_rel^rel, nodes]
when [true, false] then set_node[a, root[b,nodes], b_rel^rel, nodes]
else set_node[root[b,nodes], root[a,nodes], a_rel^b_rel^rel, nodes]
end
end
[nodes, incons]
end
find_mosoon = ->arrs do
rels = ->s { s.map(&:split).map {|a,b,rel| [a.to_i, b.to_i, (rel=="f"? 0:1)] } }
init = ->n { (1..n).reduce({}) {|a,e| a[e]={root:e}; a } }
rel_info = rels[arrs]; size,line = rel_info[0];
result = (1..line).reduce([init[size],[]]) {|a,nth| chk_cons[nth, rel_info, *a] }
result[1].size > 0 ? result[1] : "THE SPY DID NOT BETRAY"
end
Test
rpt1 = ["3 3", "1 2 f", "2 3 e", "1 3 f"]
rpt2 = ["5 7", "1 2 f", "3 4 e", "4 5 f", "2 4 e", "1 3 e", "1 4 e", "5 3 e"]
rpt3 = ["5 7", "1 2 f", "3 4 e", "4 5 f", "2 4 e", "1 3 f", "1 4 e", "5 3 e"]
rpt4 = ["5 7", "2 1 f", "3 4 e", "4 5 f", "2 4 e", "1 3 f", "1 4 e", "5 3 e"]
expect(find_mosoon[rpt1]).to eq [3] #모순
expect(find_mosoon[rpt2]).to eq [5] #모순, 다중 병합.
expect(find_mosoon[rpt3]).to eq "THE SPY DID NOT BETRAY" #정상, 다중 병합.
expect(find_mosoon[rpt4]).to eq "THE SPY DID NOT BETRAY" #정상, 노드순서 뒤집힌 경우.
Out
rpt1 = ["3 3", "1 2 f", "2 3 e", "1 3 f"]
rpt2 = ["5 7", "1 2 f", "3 4 e", "4 5 f", "2 4 e", "1 3 e", "1 4 e", "5 3 e"]
rpt3 = ["5 7", "1 2 f", "3 4 e", "4 5 f", "2 4 e", "1 3 f", "1 4 e", "5 3 e"]
rpt4 = ["5 7", "2 1 f", "3 4 e", "4 5 f", "2 4 e", "1 3 f", "1 4 e", "5 3 e"]
puts find_mosoon[rpt1], find_mosoon[rpt2], find_mosoon[rpt3], find_mosoon[rpt4]
3
5
THE SPY DID NOT BETRAY
THE SPY DID NOT BETRAY
from itertools import combinations
class paradox(BaseException):
def __init__(self):pass
class person():
def __init__(self):
self.relationDict = {}
def addRelation(self, target, relation):
srd = self.relationDict
trd = target.relationDict
if target not in srd and self not in trd:
srd[target] = trd[self] = relation
elif target in srd and self in trd:
if not ((relation == srd[target]) and (srd[target] == trd[self]) and (trd[self] == relation)):
raise paradox
return
self.refresh(); target.refresh()
def refresh(self):
combs = combinations(self.relationDict.keys(), 2)
for A, B in combs:
relation = self.relationDict[A]*self.relationDict[B]
try: A.addRelation(B, relation)
except paradox: raise paradox
while __name__ == '__main__':
n, m = list(int(x) for x in (input(">>>")).split())
plist = list(person() for x in range(n)); inlist = []
for times in range(m):
a, b, x = input(str(times+1)+':').split()
inlist.append((int(a)-1,int(b)-1,(1 if x=='f' else -1)))
for times, (left, right, relation) in enumerate(inlist):
try:
plist[left].addRelation(plist[right], relation)
except paradox:
print(times+1)
break
else:print("THE SPY DID NOT BETRAY")
더럽게 어렵네요. 파이썬 3.5.1 입니다.
정치인은 자신의 이름, 그리고 자신의 친구의 집합, 자신의 적의 집합을 구성 요소로 갖는다고 봅니다. 그리고 기본적으로 자기 자신과는 적이될 수 없으므로 초기 상태는 자신을 요소로 하는 1개짜리 집합과 비어있는 적 집합을 갖습니다.
A, B 두 정치인을 연결할 때 A <- B 로 친구 관계라면, 각각의 친구와 적 집합이 합쳐지고, A, B는 동일 객체를 참조하게 되는 것으로 변경합니다.
만약 A, B의 관계가 적이라면 친구와 적을 교대로 합해주고, B는 A의 반전 상태를 참조하게합니다.
주어진 1~n 까지의 각 정치인을 이름(숫자값)을 키로 하는 사전에 밀어넣고 제시되는 명령에 따라 합쳐나가면서 이를 검증하였습니다.
class Pol:
def __init__(self, name):
self.f = set([name])
self.e = set()
def add(self, x, f=True):
if f:
self.f = self.f.union(x.f)
self.e = self.e.union(x.e)
else:
self.f = self.f.union(x.e)
self.e = self.f.union(x.f)
def has_info(self, b):
if b in self.f:
return 1
if b in self.e:
return -1
return 0
def reversed(self, name):
x = Pol(name)
x.e = self.f
x.f = self.e
return x
np = 5
sample = """\
1 2 f
3 4 e
4 5 f
2 4 e
1 3 e
1 4 e
5 3 e"""
def main():
data = dict((x+1, Pol(x+1)) for x in range(np))
for i, cmd in enumerate(sample.split('\n')):
a, b, f = cmd.split()
a, b = int(a), int(b)
f = f == 'f'
if f:
if data[a].has_info(b) == 1:
pass
elif data[a].has_info(b) == -1:
print("Betray: {}) {} => {} | {}".format(i+1, a, b, "f" if f else "e"))
break
else:
data[a].add(data[b], True)
data[b] = data[a]
else:
if data[a].has_info(b) == -1:
pass
elif data[a].has_info(b) == 1:
print("Betray: {}) {} => {} | {}".format(i+1, a, b, "f" if f else "e"))
break
else:
data[a].add(data[b], False)
data[b] = data[a].reversed(b)
else:
print("THE SPY DID NOT BETRAY")
main()
class Person:
def __init__(self,n,m):
self.n=n;
self.m=m;
self.L=[[],[]]
self.b=0
self.e=m
def Execute(self):
self.InPut_Person()
def InPut_Person(self):
for i in range(0,self.m):
n=raw_input().split(' ')
if 'f' in n:
self.Add_friend(n)
elif 'e' in n:
self.Add_enemy(n)
self.Check_Spy(i+1)
print self.e
def Add_friend(self,n):
if(n[0] in self.L[0]):
self.L[0].append(n[1])
elif(n[0] in self.L[1]):
self.L[1].append(n[1])
else:
self.L[0].append(n[0])
self.L[0].append(n[1])
def Add_enemy(self,n):
if(n[0] in self.L[0]):
if(n[1] not in self.L[1]):
self.L[1].append(n[1])
elif(n[0] in self.L[1]):
if(n[1] not in self.L[0]):
self.L[0].append(n[1])
else:
self.L[0].append(n[0])
self.L[1].append(n[1])
def Check_Spy(self,n):
for i in self.L[0]:
if i in self.L[1]:
self.b=1
break
if self.b==0:
self.e="THE SPY DID NOT BETRAY"
if self.b==1:
if(n<self.e):
self.e=n
3 3 1 2 f 2 3 e 1 3 f
1 번째 모순 여부 : 1
2 번째 모순 여부 : 1
5 7 1 2 f 3 4 e 4 5 f 2 4 e 1 3 e 1 4 e 5 3 e 1 번째 모순 여부 : 1
2 번째 모순 여부 : 1
3 번째 모순 여부 : 0
4 번째 모순 여부 : 1
5 번째 모순 여부 : 0
6 번째 모순 여부 : 0
7 번째 모순 여부 : 0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_COLS 100000
/*
나의 친구의 친구는 나의 친구이다.
나의 친구의 적은 나의 적이다.
나의 적의 친구는 나의 적이다.
나의 적의 적은 나의 친구이다.
*/
int M, N;
char** relation;
void init();
bool find_betray();
void printr();
void main() {
FILE* f = fopen("input.txt", "r");
char s[MAX_COLS];
int i = 0;
while(fgets(s, MAX_COLS, f)) {
if(!i) {
N = s[0]-48;
M = s[2]-48;
init();
}
else {
relation[s[0]-48][s[2]-48] = s[4];
relation[s[2]-48][s[0]-48] = s[4];
printf("%d 번째 모순 여부 : %d \n\n",i, find_betray());
printr();
}
i++;
}
}
void init() {
relation = (char**) malloc (sizeof(char*) * N+1);
for(int i=0;i<= N ;i++)
relation[i] = (char*) malloc (sizeof(char) * N+1);
for(int i=0;i<= N ;i++) {
for(int j=0;j<= N ;j++) {
relation[i][j] = NULL;
}
}
}
bool find_betray(){
for(int i=1;i<= N ;i++) {
for(int j=1;j<= N ;j++) {
if(relation[i][j]=='f') { // i, j의 친구의 친구는 친구다
for(int k=1 ;k<= N; k++)
if(relation[j][k] == 'f' && i!=k) {
if(relation[k][i]=='e' || relation[i][k]=='e')
return false;
relation[i][k] = 'f';
relation[k][i] = 'f';
}
for(int k=1 ;k<= N; k++)
if(relation[i][k] == 'f' && j!=k) {
if(relation[k][j]=='e' || relation[j][k]=='e')
return false;
relation[k][j] = 'f';
relation[j][k] = 'f';
}
}
if(relation[i][j]=='f') { // i, j의 친구의 적는 적이다
for(int k=1 ;k<= N; k++)
if(relation[j][k] == 'e' && i!=k) {
if(relation[k][i]=='f' || relation[i][k]=='f')
return false;
relation[i][k] = 'e';
relation[k][i] = 'e';
}
for(int k=1 ;k<= N; k++)
if(relation[i][k] == 'e' && j!=k) {
if(relation[k][j]=='f' || relation[j][k]=='f')
return false;
relation[k][j] = 'e';
relation[j][k] = 'e';
}
}
if(relation[i][j]=='e') { // 나의 적의 친구는 나의 적이다.
for(int k=1 ;k<= N; k++)
if(relation[j][k] == 'f' && i!=k) {
if(relation[k][i]=='f' || relation[i][k]=='f')
return false;
relation[i][k] = 'e';
relation[k][i] = 'e';
}
for(int k=1 ;k<= N; k++)
if(relation[i][k] == 'f' && j!=k) {
if(relation[k][j]=='f' || relation[j][k]=='f')
return false;
relation[k][j] = 'e';
relation[j][k] = 'e';
}
}
if(relation[i][j]=='e') { //나의 적의 적은 나의 친구이다..
for(int k=1 ;k<= N; k++)
if(i!=k && relation[j][k] == 'e') {
if(relation[k][i]=='e' || relation[i][k]=='e')
return false;
relation[i][k] = 'f';
relation[k][i] = 'f';
}
for(int k=1 ;k<= N; k++)
if(relation[i][k] == 'e' && j!=k) {
if(relation[k][j]=='e' || relation[j][k]=='e')
return false;
relation[k][j] = 'f';
relation[j][k] = 'f';
}
}
}
}
return true;
}
void printr() {
for(int i=1;i<= N ;i++) {
for(int j=1;j<= N ;j++) {
if(i!=j)
printf("%d %d ,%c\n" , i, j, relation[i][j]);
}
}
}
3 3 1 2 f 2 3 e 1 3 f
1 번째 모순 여부 : 1
2 번째 모순 여부 : 1
5 7 1 2 f 3 4 e 4 5 f 2 4 e 1 3 e 1 4 e 5 3 e 1 번째 모순 여부 : 1
2 번째 모순 여부 : 1
3 번째 모순 여부 : 0
4 번째 모순 여부 : 1
5 번째 모순 여부 : 0
6 번째 모순 여부 : 0
7 번째 모순 여부 : 0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_COLS 100000
/*
나의 친구의 친구는 나의 친구이다.
나의 친구의 적은 나의 적이다.
나의 적의 친구는 나의 적이다.
나의 적의 적은 나의 친구이다.
*/
int M, N;
char** relation;
void init();
bool find_betray();
void printr();
void main() {
FILE* f = fopen("input.txt", "r");
char s[MAX_COLS];
int i = 0;
while(fgets(s, MAX_COLS, f)) {
if(!i) {
N = s[0]-48;
M = s[2]-48;
init();
}
else {
relation[s[0]-48][s[2]-48] = s[4];
relation[s[2]-48][s[0]-48] = s[4];
printf("%d 번째 모순 여부 : %d \n\n",i, find_betray());
printr();
}
i++;
}
}
void init() {
relation = (char**) malloc (sizeof(char*) * N+1);
for(int i=0;i<= N ;i++)
relation[i] = (char*) malloc (sizeof(char) * N+1);
for(int i=0;i<= N ;i++) {
for(int j=0;j<= N ;j++) {
relation[i][j] = NULL;
}
}
}
bool find_betray(){
for(int i=1;i<= N ;i++) {
for(int j=1;j<= N ;j++) {
if(relation[i][j]=='f') { // i, j의 친구의 친구는 친구다
for(int k=1 ;k<= N; k++)
if(relation[j][k] == 'f' && i!=k) {
if(relation[k][i]=='e' || relation[i][k]=='e')
return false;
relation[i][k] = 'f';
relation[k][i] = 'f';
}
for(int k=1 ;k<= N; k++)
if(relation[i][k] == 'f' && j!=k) {
if(relation[k][j]=='e' || relation[j][k]=='e')
return false;
relation[k][j] = 'f';
relation[j][k] = 'f';
}
}
if(relation[i][j]=='f') { // i, j의 친구의 적는 적이다
for(int k=1 ;k<= N; k++)
if(relation[j][k] == 'e' && i!=k) {
if(relation[k][i]=='f' || relation[i][k]=='f')
return false;
relation[i][k] = 'e';
relation[k][i] = 'e';
}
for(int k=1 ;k<= N; k++)
if(relation[i][k] == 'e' && j!=k) {
if(relation[k][j]=='f' || relation[j][k]=='f')
return false;
relation[k][j] = 'e';
relation[j][k] = 'e';
}
}
if(relation[i][j]=='e') { // 나의 적의 친구는 나의 적이다.
for(int k=1 ;k<= N; k++)
if(relation[j][k] == 'f' && i!=k) {
if(relation[k][i]=='f' || relation[i][k]=='f')
return false;
relation[i][k] = 'e';
relation[k][i] = 'e';
}
for(int k=1 ;k<= N; k++)
if(relation[i][k] == 'f' && j!=k) {
if(relation[k][j]=='f' || relation[j][k]=='f')
return false;
relation[k][j] = 'e';
relation[j][k] = 'e';
}
}
if(relation[i][j]=='e') { //나의 적의 적은 나의 친구이다..
for(int k=1 ;k<= N; k++)
if(i!=k && relation[j][k] == 'e') {
if(relation[k][i]=='e' || relation[i][k]=='e')
return false;
relation[i][k] = 'f';
relation[k][i] = 'f';
}
for(int k=1 ;k<= N; k++)
if(relation[i][k] == 'e' && j!=k) {
if(relation[k][j]=='e' || relation[j][k]=='e')
return false;
relation[k][j] = 'f';
relation[j][k] = 'f';
}
}
}
}
return true;
}
void printr() {
for(int i=1;i<= N ;i++) {
for(int j=1;j<= N ;j++) {
if(i!=j)
printf("%d %d ,%c\n" , i, j, relation[i][j]);
}
}
}
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <windows.h>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <list>
using namespace std;
struct stBet {
int a, b;
char fore;
};
int main(void)
{
int m, n; //m : 정치인의 수 , n : 처리 명령의 수
cin >> m >> n;
if (m > 100000 || n > 1000000) {
cout << "정치인의수, 명령의수 범위 초과" << endl;
return 0;
}
list<stBet> Betlist;
list<stBet>::iterator iter1 = Betlist.begin();
list<stBet>::iterator iter2 = Betlist.begin();
list<stBet>::iterator iter3 = Betlist.begin();
stBet stBet;
for (int i = 0; i < n; i++) {
cin >> stBet.a >> stBet.b >> stBet.fore;
if (stBet.a > m || stBet.b > m || (stBet.fore != 'f' && stBet.fore != 'e')) {
cout << "잘못 된 입력 " << endl;
return 0;
}
Betlist.push_back(stBet);
}
int itcount = 0;
bool esc = false;
for (iter1 = Betlist.begin(); iter1 != Betlist.end(); iter1++)
{
itcount++;
for (iter2 = Betlist.begin(); iter2 != iter1; iter2++) {
if (((*iter1).a == (*iter2).a && (*iter1).b == (*iter2).b) ||
((*iter1).a == (*iter2).b && (*iter1).b == (*iter2).a)) {
if ((*iter1).fore != (*iter2).fore) {
cout << itcount << endl;
esc = true;
break;
}
else {
Betlist.erase(iter2);
iter2 = Betlist.begin();
//이부분 iter2를 맨 처음위치로 돌려놓지 않으면 에러발생
//값을 지웠기때문에 아래부분에서 없는 값을 참조해 if문을 하기떄문
}
}
if ((*iter1).a == (*iter2).a) {
stBet.a = (*iter1).b;
stBet.b = (*iter2).b;
if ((*iter1).fore == (*iter2).fore) {
stBet.fore = 'f';
}
else {
stBet.fore = 'e';
}
Betlist.push_front(stBet);
for (iter3 = Betlist.begin(); iter3 != iter1; iter3++) {
if ((*iter3).a == (*Betlist.begin()).a && (*iter3).b == (*Betlist.begin()).b ||
(*iter3).a == (*Betlist.begin()).b && (*iter3).b == (*Betlist.begin()).a) {
if ((*iter3).fore != (*Betlist.begin()).fore) {
cout << itcount << endl;
esc = true;
break;
}
}
}
if (esc)break;
}
if ((*iter1).a == (*iter2).b) {
stBet.a = (*iter1).b;
stBet.b = (*iter2).a;
if ((*iter1).fore == (*iter2).fore) {
stBet.fore = 'f';
}
else {
stBet.fore = 'e';
}
Betlist.push_front(stBet);
for (iter3 = Betlist.begin(); iter3 != iter1; iter3++) {
if ((*iter3).a == (*Betlist.begin()).a && (*iter3).b == (*Betlist.begin()).b ||
(*iter3).a == (*Betlist.begin()).b && (*iter3).b == (*Betlist.begin()).a) {
if ((*iter3).fore != (*Betlist.begin()).fore) {
cout << itcount << endl;
esc = true;
break;
}
}
}
if (esc) break;
}
if ((*iter1).b == (*iter2).a) {
stBet.a = (*iter1).a;
stBet.b = (*iter2).b;
if ((*iter1).fore == (*iter2).fore) {
stBet.fore = 'f';
}
else {
stBet.fore = 'e';
}
Betlist.push_front(stBet);
for (iter3 = Betlist.begin(); iter3 != iter1; iter3++) {
if ((*iter3).a == (*Betlist.begin()).a && (*iter3).b == (*Betlist.begin()).b ||
(*iter3).a == (*Betlist.begin()).b && (*iter3).b == (*Betlist.begin()).a) {
if ((*iter3).fore != (*Betlist.begin()).fore) {
cout << itcount << endl;
esc = true;
break;
}
}
}
if (esc) break;
}
if ((*iter1).b == (*iter2).b) {
stBet.a = (*iter1).a;
stBet.b = (*iter2).a;
if ((*iter1).fore == (*iter2).fore) {
stBet.fore = 'f';
}
else {
stBet.fore = 'e';
}
Betlist.push_front(stBet);
for (iter3 = Betlist.begin(); iter3 != iter1; iter3++) {
if ((*iter3).a == (*Betlist.begin()).a && (*iter3).b == (*Betlist.begin()).b ||
(*iter3).a == (*Betlist.begin()).b && (*iter3).b == (*Betlist.begin()).a) {
if ((*iter3).fore != (*Betlist.begin()).fore) {
cout << itcount << endl;
esc = true;
break;
}
}
}
if (esc) break;
}
}
if (esc) break;
}
if (!esc) {
cout << "THE SPY DID NOT BETRAY" << endl;
}
system("pause");
return 0;
}
관계입력은 사람순서, 친구적 설정은 랜덤으로 하는식으로 바꿔서 했습니다.. ㅠㅠ 풀었다고 할 순 없네요 .... 일단 저장
public class Test {
final static int en = -1;
final static int fd = 1;
static boolean spyLie = false;
static int pcount = 0;
static long[][] relTable = null;
static int occurA=0;
static int occurB=0;
public static void Excute(int person,int exCount){
pcount = person+1;
relTable = new long[pcount][pcount];
int c=0;
pRow:
for(int row=0;row<pcount;row++){
In:
for(int cal = 0;cal<pcount;cal++){
int r = getRanRelation();
if(row == 0 || cal == 0 || row == cal){
relTable[row][cal] = 0;
continue In;
}
c++;
if(c >= exCount){
break pRow;
}
System.out.print("["+c+"] 번째 수행 : ");
System.out.println(row+" @ "+cal+" = "+getRname(r));
relTable[row][cal] = r;
spyLie = chkMo(r,row,cal);
if(spyLie == true){
break pRow;
}
}
}
// 최종
if(spyLie == false){
System.out.println("THE SPY DID NOT BETRAY");
}else{
System.out.println("## Error ! : 스파이가 거짓말을 합니다.");
int o = occurB-occurA;
int n = ((occurA-1)*person)+occurB;
if(o>0) n = n - occurA;
else n = n - (occurA-1);
System.out.println("## ["+n+"번째 수행에서 첫번째 발생] "+occurA+" 와 "+occurB+" 의 관계가 모순입니다.!");
}
}
public static String getRname(int r){
if(r == fd)return "친구";
else return "적";
}
public static int getRanRelation(){
int r = 0;
while(r == 0)r = (int) (Math.random() * (3)) -1;
return r;
}
public static void main(String[] args) {
Excute(10000,100000);
}
public static boolean chkMo(int r,int a,int b){
boolean x = false;
for(int i=0;i<pcount;i++){
if(i == 0) continue;
int k = (int) (relTable[a][i]*relTable[b][i]);
if(k == 0) continue;
else if(k == r)continue;
else{
if(a <b){
occurA = a;
}else{
occurA = b;
}
occurB = i;
x = true;
break;
}
}
return x;
}
}
친구'들'을 한 당(집합)으로 만들면 그래프 문제가 아니라 (집합 -적대관계- 집합) 의 배타적인 쌍의 문제가 됩니다.
입력이 들어올 때마다 합당을 해 주면 적의 적의 적의 친구... 같은 복잡한 관계는 발생하지 않고
한 다리만 건너서 친구의 적, 적의 적만 고려하면 됩니다.
.
처음에 인원수가 한 명 뿐인 당들을 만들고 시작합니다.
입력: a와 b가 친구 -> a가 속한 A당과 b가 속한 B당, (A당의 적당)과 (B당의 적당)을 각각 합당합니다.
(이미 같은 당이면 필요 없음)
입력: a와 b가 적 -> a가 속한 A당과 (b가 속한B당의 적당), B당과 (A당의 적당)을 각각 합당합니다.
(이미 서로 적이면 필요 없음)
모순은 a와 b가 친구라고 입력됐는데 이미 적인 경우와, 적이라고 입력됐는데 이미 친구인 경우 밖에 없습니다.
.
구현에 있어서는 특정 당에 속한 정치가들과, 특정 정치가가 속한 당을 모두 알아야 하기 때문에 양방향 포인터를 유지해야 합니다.
객체를 만들어서 해 봤는데 아직 익숙치 않아서 좀 고생했네요.
merge 대신 merged로 만들면 좀 더 깔끔해질 거 같습니다.
class Party:
def __init__(self, p):
self.members = {p}
self.enemy = None
def __eq__(self, other):
return self.members == other.members
def merge(self, other): # 합당이 아니라 흡당(?)이라고 해야 정확할 듯
if other:
self.members |= other.members
for p in other.members:
p.party = self
def be_friend_of(self, other):
if not (self == other):
self.merge(other)
if not self.enemy: self.enemy = other.enemy
else: self.enemy.merge(other.enemy)
def be_enemy_of(self, other):
if not (self.enemy and self.enemy == other):
if not self.enemy: self.enemy = other
else: self.enemy.merge(other)
if not other.enemy: other.enemy = self
else: other.enemy.merge(self)
class Politician:
def __init__(self, id):
self.id = id
self.party = Party(self)
def enemy_of(self, other):
return self.party.enemy and self.party.enemy == other.party
def friend_of(self, other):
return self.party == other.party
#data = '3 3\n1 2 f\n2 3 e\n1 3 f'
data = '5 7\n1 2 f\n3 4 e\n4 5 f\n2 4 e\n1 3 e\n1 4 e\n5 3 e'
lines = data.split('\n')
N, M = map(int, lines[0].split())
politicians = [Politician(i + 1) for i in range(N)]
cline = 0
for m in range(1, M + 1):
line = lines[m].split()
p1, p2, r = politicians[int(line[0])-1], politicians[int(line[1])-1], line[2]
if r == 'e' and p1.friend_of(p2) or r == 'f' and p1.enemy_of(p2):
cline = m
break
if r == 'f': p1.party.be_friend_of(p2.party)
else: p1.party.be_enemy_of(p2.party)
print(cline if cline else "THE SPY DID NOT BETRAY")
import numpy as np
a, b = input().split()
a = int(a)
b = int(b)
b_list = np.zeros((b, 3), dtype = 'U')
a_list = np.zeros((a, a))
nalji = True
for i in range(b):
q, w, e = input().split()
b_list[i][0] = q
b_list[i][1] = w
b_list[i][2] = e
for i in range(b):
q = b_list[i][0]
q = int(q)
w = b_list[i][1]
w = int(w)
e = b_list[i][2]
if e == "f":
a_list[q-1][w-1] = 1
else:
a_list[q-1][w-1] = -1
for q in range(a):
for w in range(a-q-1):
for e in range(a-w-2):
if a_list[q][w+1] * a_list[q][e+2] == -1:
nalji = False
break
if nalji == False:
break
if nalji == False:
break
if nalji == False:
print(i+1)
break
if nalji == True:
print("THE SPY DID NOT BETRAY")
'''
친구사이가 1 이고 적인 사이가 0 일 때, 0과 1 또는 1과 0이 만나면 1이 되고,
1과 1 또는 0과 0이 만나면 1이 되는 연산은 Exlusive OR 의 부정(XNOR)이다.
나의 친구의 친구는 나의 친구이다. (1 XNOR 1) -> 1
나의 친구의 적은 나의 적이다. (1 XNOR 0) -> 0
나의 적의 친구는 나의 적이다. (0 XNOR 1) -> 0
나의 적의 적은 나의 친구이다. (0 XNOR 0) -> 1
1 - (1 ^ 1) -> 1
1 - (1 ^ 0) -> 0
1 - (0 ^ 1) -> 0
1 - (0 ^ 0) -> 1
맨먼저 힌트로 주어진 것을 이용하여 아래의 relation map 을 채우고,
그 다음 자신(1)과 관계가 있는 사람(a : 나와의 관계가 친구 또는 적)의 다른 사람(2)과의 관계(b : 친구 또는 적)들을 참조하여,
a 관계와 b 관계를 XNOR 연산한 결과를 (1)과 (2)사이의 관계 map 에 채우는 방법으로 하면 된다.
1 2 3 4 5 (people)
---------------------------
1 | 1 1 1 0 0 (1: 친구사이, 0:적)
2 | 1 1 1 0 0
3 | 1 1 1 0 0
4 | 0 0 0 1 1
5 | 0 0 0 1 1
'''
import numpy as np
succ = 1
fail = 0
def setGivenReport( m, h, idx ):
# print("{} : {} {} {}".format(i, h[idx][0], h[idx][1], h[i][2]))
if h[idx][2] == 'f':
val = 1
else:
val = 0
row = h[idx][0]-1
col = h[idx][1]-1
# 주어진 보고 값과 이미 셋팅된 값이 다를 경우 모순 보고
if np.isnan(m[row,col]) != 1:
if m[row,col] != val:
return fail
m[ row, col ] = val
m[ col, row ] = val
return succ
# 기존 보고를 통해 다른 관계들을 채워넣음
def updateRelation( m ):
for row in range(len(m)):
for col in range(len(m)):
if row != col:
if np.isnan(m[row,col]) != 1:
x = int(m[row,col])
#print("-> [{},{}] = {}".format(row,col,x))
for row2 in range(len(m)):
#print(" -> [{},{}] = {}".format(row2,col,m[row2,col]))
if row2 != col:
if row2 != row:
if np.isnan(m[row2,col]) != 1:
y = int(m[row2,col])
val = 1 - (x ^ y)
m[row,row2] = val
def doit( sz, h ):
print("\n==========\n");
m = np.empty((sz,sz))
m.fill(np.nan)
# 자신은 항상 친구
for i in range(len(m)):
m[i][i] = 1
for i in range(len(h)):
ret = setGivenReport( m, h, i )
if ret == fail:
print("*** {} th Report is not valid".format(i+1));
break
updateRelation( m )
print("{}\n".format(m))
p1 = 3 # number of people
r1 = [ [1,2,'f'], # Report
[2,3,'e'],
[1,3,'f'] ]
p2 = 5
r2 = [ [1,2,'f'],
[3,4,'e'],
[4,5,'f'],
[2,4,'e'],
[1,3,'e'],
[1,4,'e'],
[5,3,'e'] ]
doit(p1,r1)
doit(p2,r2)
메모리 사용량 줄이기 위해 비트배열로 풀었습니다
시간복잡도도 좀 더 줄일수 있을거 같은데 제 지식으로는 힘드네요ㅜ
def spycheck(n,r):
c = 1
if r[0][2] == 'f': eflist = 2**r[0][0] + 2**r[0][1]
else: eflist = 2**r[0][0]
memberlist = 2**r[0][0] + 2**r[0][1]
check = lambda x: int(bin(memberlist)[2:][-(x+1)]) if x+1 <= len(bin(memberlist))-2 else 0
efcheck = lambda x: int(bin(eflist)[2:][-(x+1)]) if x+1 <= len(bin(eflist))-2 else 0
while c < len(r):
for i in range(c,len(r)):
if check(r[i][0]) == 0 and check(r[i][1]) == 0: continue
elif check(r[i][0]) == 1 and check(r[i][1]) == 0:
if i == c: c += 1
memberlist += 2**r[i][1]
if r[i][2] == 'f':
if efcheck(r[i][0]) == 1: eflist += 2**r[i][1]
else:
if efcheck(r[i][0]) == 0: eflist += 2**r[i][1]
break
elif check(r[i][0]) == 0 and check(r[i][1]) == 1:
if i == c: c += 1
memberlist += 2**r[i][0]
if r[i][2] == 'f':
if efcheck(r[i][1]) == 1: eflist += 2**r[i][0]
else:
if efcheck(r[i][1]) == 0: eflist += 2**r[i][0]
break
else:
if i == c: c += 1
if r[i][2] == 'f':
if efcheck(r[i][0]) != efcheck(r[i][1]): return i+1
else:
if efcheck(r[i][0]) == efcheck(r[i][1]): return i+1
break
return "THE SPY DID NOT BETRAY"
n,m = map(int,input().split())
report = []
for i in range(m):
report.append([int(i) if i.isdigit() else i for i in input().split()])
print(f'\n>>> {spycheck(n,report)}')
test_spy <- function(nat_first, nat_second, tof, cnt){
nat <<- nat
if (cnt == 1){
if (tof == 'f'){
nat[nat_first] <<- nat[nat_second] <<- 1
} else if (tof == 'e'){
nat[nat_first] <<- 1
nat[nat_second] <<- -1
}
return(TRUE)
}
if (nat[nat_first] == 0){
if (tof == 'e'){
nat[nat_first] <<- nat[nat_second] * (-1)
} else if (tof == 'f'){
nat[nat_first] <<- nat[nat_second]
}
return(TRUE)
} else if (nat[nat_second] == 0){
if (tof == 'e'){
nat[nat_second] <<- nat[nat_first] * (-1)
} else if (tof == 'f'){
nat[nat_second] <<- nat[nat_first]
}
return(TRUE)
} else {
if (tof == 'e' & nat[nat_first] != nat[nat_second]){
return(TRUE)
} else if (tof == 'f' & nat[nat_first] == nat[nat_second]){
return(TRUE)
} else {
print(paste(cnt, ' is contradiction', sep = ''))
return(FALSE)
}
}
}
n <- 3
nat <- rep(0, n)
info_spy <- matrix(c(1, 2, 'f',
2, 3, 'e',
1, 3, 'f'), nrow = 3, byrow = T)
for (i in seq(n)){
nat_f <- as.numeric(info_spy[i, 1])
nat_s <- as.numeric(info_spy[i, 2])
tof <- info_spy[i, 3]
r_spy <- test_spy(nat_f, nat_s, tof, i)
if (r_spy){
} else {
break
}
}
Python 3.7
* (-1), 친구인 경우 * 1 하여 사전에 저장된 값과 보고된 값 비교def main():
_, num_reports = map(int, input().strip().split())
reports = [] # 리포트 문자열 저장
for _ in range(num_reports):
reports.append(input().strip())
relations = dict() # 사전 - 신규 키(정치인) 성향(1)에 대한 상대적 성향(친구=1 | 적=-1)
mismatch_num = 0 # 불일치 발생 보고의 회차
for i, report in enumerate(reports):
a, b, x = report.strip().split() # a, b, x
rel_stat = 1 if x == "f" else -1 # 친구 => 1, 적 => -1
relations.setdefault(a, 1) # a => 신규 정치인일 경우 성향(1)
# b 정치인 성향 = a 정치인 성향 * (친구 = 1 | 적인 경우 = -1)
relations.setdefault(b, relations[a] * rel_stat) # b => 신규 정치인일 경우
# 존재하는 b 키에 대해 새로 보고된 적아 구분(1 or -1)이 다를 경우
if relations[a] * rel_stat != relations[b]:
mismatch_num = i + 1
break
print(mismatch_num if mismatch_num > 0 else "THE SPY DID NOT BETRAY")
if __name__ == "__main__":
main()
/* 전제 조건 1.친구의 친구는 친구다 2.친구의 적은 적이다 3.적의 친구는 적이다 4.적의 적은 친구다
입력 예제 3 3 1 2 f 2 3 e 1 3 f
출력 예제 3 해설) 1과 2는 친구이고 2와 3이 적이므로 1과 3은 서로 적이어야 한다. */
import java.util.ArrayList; import java.util.List; import java.util.Scanner;
// 정치인을 Node로 정리 class Node {
int seq;
List<Node> FriendList;
List<Node> EnemyList;
Node(int seq) {
this.seq = seq;
FriendList = new ArrayList<Node>();
EnemyList = new ArrayList<Node>();
}
int getSeq() {
return this.seq;
}
void addFriend(Node f) {
FriendList.add(f);
}
void addEnemy(Node e) {
EnemyList.add(e);
}
List<Node> getFriendList(){
return this.FriendList;
}
List<Node> getEnemyList(){
return this.EnemyList;
}
};
public class sol033_thinkBig {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정치인 수
List<Node> people = new ArrayList<Node>();
for(int i=0; i<n; i++) {
people.add(new Node(i+1));
}
int m = sc.nextInt(); // 첩보 갯수
sc.nextLine();
// 첩보 처리
for(int i=0; i<m; i++) {
String command[] = sc.nextLine().split(" ");
int left = Integer.parseInt(command[0]);
int right = Integer.parseInt(command[1]);
// 친구면 true, 적이면 false
boolean friend = command[2].trim().equals("f") ? true : false;
Node leftNode = null; // 첩보의 왼쪽 정치인
Node rightNode = null; // 첩보의 오른쪽 정치인
for(int j=0; j<people.size(); j++) {
if(people.get(j).getSeq() == left) leftNode = people.get(j);
if(people.get(j).getSeq() == right) rightNode = people.get(j);
}
// 친구관계라면 친구관계 저장
if(friend) {
leftNode.addFriend(rightNode);
rightNode.addFriend(leftNode);
}
// 적관계라면 적관계 저장
else {
leftNode.addEnemy(rightNode);
rightNode.addEnemy(leftNode);
}
}
// 배신 결과 처리 , 모든 people의 친구목록과 적목록을 봐야함
getResult : {
for(int i=0; i<people.size(); i++) {
System.out.println("###############");
System.out.println(people.get(i).getSeq());
List<Node> friends = people.get(i).getFriendList(); // 검사 노드의 친구 List
List<Node> Enemies = people.get(i).getEnemyList(); // 검사 노드의 적 List
// 특정 Node의 친구 List
for(int j=0; j<friends.size(); j++) {
System.out.println(" f " + friends.get(j).getSeq());
List<Node> friends_friends = friends.get(j).getFriendList();
List<Node> friends_enemies = friends.get(j).getEnemyList();
// 1.친구의 친구는 친구다 검증
for(int k=0; k<friends_friends.size(); k++) {
System.out.println(" f " + friends_friends.get(k).getSeq());
// 친구의 친구가 적으로 등록되어있으면 배신 검토
for(int l=0; l<Enemies.size(); l++) {
if(Enemies.get(l).getSeq() == friends_friends.get(k).getSeq()) {
System.out.println(people.get(i).getSeq() + "과" + Enemies.get(l).getSeq() +"는 친구 관계여야함 -- 배신자");
break getResult;
}
}
}
// 2.친구의 적은 적이다 검증
for(int k=0; k<friends_enemies.size(); k++) {
System.out.println(" e " + friends_enemies.get(k).getSeq());
// 친구의 적이 친구로 등록되어있으면 배신 검토
for(int l=0; l<friends.size(); l++) {
if(friends.get(l).getSeq() == friends_enemies.get(k).getSeq()) {
System.out.println(people.get(i).getSeq() + "과" + friends.get(l).getSeq() +"는 적 관계여야함 -- 배신자");
break getResult;
}
}
}
}
// 특정 Node의 적 List
for(int j=0; j<Enemies.size(); j++) {
System.out.println(" e " + Enemies.get(j).getSeq());
List<Node> enemies_friends = Enemies.get(j).getFriendList();
List<Node> enemies_enemies = Enemies.get(j).getEnemyList();
// 3.적의 친구는 적이다
for(int k=0; k<enemies_friends.size(); k++) {
System.out.println(" f " + enemies_friends.get(k).getSeq());
// 적의 친구가 친구로 등록되어있으면 배신 검토
for(int l=0; l<friends.size(); l++) {
if(friends.get(l).getSeq() == enemies_friends.get(k).getSeq()) {
System.out.println(people.get(i).getSeq() + "과" + friends.get(l).getSeq() +"는 적 관계여야함 -- 배신자");
break getResult;
}
}
}
//4.적의 적은 친구다
for(int k=0; k<enemies_enemies.size(); k++) {
System.out.println(" e " + enemies_enemies.get(k).getSeq());
// 적의 적이 적으로 등록되어있으면 배신 검토
for(int l=0; l<Enemies.size(); l++) {
if(Enemies.get(l).getSeq() == enemies_enemies.get(k).getSeq()) {
System.out.println(people.get(i).getSeq() + "과" + Enemies.get(l).getSeq() +"는 친구 관계여야함 -- 배신자");
break getResult;
}
}
}
}
}
System.out.println("배신하지 않음");
}
System.out.println("#########첩보 정리##########");
for(int i=0; i<people.size(); i++) {
System.out.print(people.get(i).getSeq() + "의 아군 : ");
List<Node> f = people.get(i).getFriendList();
for(int j=0; j<f.size(); j++) {
System.out.print(f.get(j).getSeq() + " ");
}
System.out.println();
System.out.print(people.get(i).getSeq() + "의 적군 : ");
List<Node> e = people.get(i).getEnemyList();
for(int j=0; j<e.size(); j++) {
System.out.print(e.get(j).getSeq() + " ");
}
System.out.println();
System.out.println("#############");
}
}
}
# 정보 입력 함수, 정보가 없거나 같은 정보가 들어오면 인정, 다른 정보가 들어오면 False를 리턴 - 스파이
def input_if(info,key,value):
if info[key] == '' or info[key] == value:
info[key] = value
return True
elif info[key] != value and info[key] != '':
return False
#입려받은 사람 수만큼 (1+2+...+n-1)개의 딕셔너리 생성
#ex(사람 수 4명 : {'12 : '' , '13' : '', '14' : '' , '23' : '' , '24 : '', '34' : ''}
num_people, num_info = map(int, input('Enter the number of people and information of them : ').split(' ')) # 사람, 정보 개수 입력
info = {}
for i in range(1, num_people+1):
for j in range(i+1, num_people+1):
info[str(i)+str(j)] = ''
result = 0
boolvar = True
for i in range(1, num_info+1): # 이미 거짓된 정보가 들어와도 입력받은 정보의 갯수만큼 받을 수 있도록 반복
temp = sorted(input().split(' '))
if not boolvar:
continue #이미 거짓이면 정보만 받고 끝
input_key = temp[0]+temp[1]
input_value = temp[2]
temp_key = []
boolvar = input_if(info,input_key,input_value) # 입력 받은 정보를 진실이면 info에 넣고 아니면 반복 끝
if not boolvar:
result = i
continue
# 입력받은 정보 삽입 후에 전체 딕셔너리를 돌면서 value가 있는 key만 검색 후 비교
for key in list(info.keys()):
if info[key]: # value가 있으면
for another in list(info.keys()):
if info[another]:
if key != another and not set(key).isdisjoint(set(another)): #서로 key가 같지 않다면
#key의 대칭차를 구함. (12와 23의 대칭차는 13임. 12와 23의 정보가 있으면 13의 정보를 알 수 있음
if info[key] == info[another] :
boolvar = input_if(info,''.join(sorted(list(set(key).symmetric_difference(set(another))))), 'f') #둘이 친구친구, 적적이면 둘은 친구임
else :
boolvar = input_if(info,''.join(sorted(list(set(key).symmetric_difference(set(another))))), 'e') #둘이 친구의적, 적의친구면 나의 적
print(info)
if not boolvar:
result = i # 거짓임이 판명 나면 그 정보의 n번째가 거짓임
if result : print(result)
else : print("THE SPY DID NOT BETRAY")
n명일 때 NxN의 행렬을 만들면 불필요한 정보가 생성되서 (1+2+...+n-1)의 딕셔너리를 만들어서 반복의 횟수를 줄이고자 했습니다. 코딩은 초보라 좀더 예쁘게 만들수가 없네요 ㅜㅜ
두 사람을 비교할 때를 3가지 경우로 나누어 생각했습니다.
f => (1번사람)=1, (2번사람)=1
e => (1번사람)=1, (2번사람) =-1
f => (1번사람) = (2번사람)
e => (1번사람) = -(2번사람)
f => (1번사람) * (2번사람) = 1
e => (1번사람) * (2번사람) = -1
N,M = map(int, input().split(' '))
report = []
person = []
for i in range(M) :
report.append(list(input().split(' ')))
for i in range(N) :
person.append(0)
ans = 0
for i in report :
ans = ans + 1
person1 = person[int(i[0])-1]
person2 = person[int(i[1])-1]
if i[2] == 'f' :
if person1 == 0 and person2 == 0 :
person[int(i[0])-1] = 1
person[int(i[1])-1] = 1
elif person1 != 0 and person2 == 0 :
person[int(i[1])-1] = person1
elif person1 == 0 and person2 != 0 :
person[int(i[0])-1] = person2
else :
if person1 * person2 == -1 :
print(ans)
ans = 0
else :
if person1 == 0 and person2 == 0 :
person[int(i[0])-1] = 1
person[int(i[1])-1] = -1
elif person1 != 0 and person2 == 0 :
person[int(i[1])-1] = -person1
elif person1 == 0 and person2 != 0 :
person[int(i[0])-1] = -person2
else :
if person1 * person2 == 1 :
print(ans)
ans = 0
if ans == M :
print("THE SPY DID NOT BETRAY")
N, M = map(int, input().split())
Mlist = [input().split() for i in range(M)]
Nlist = [0] * (N + 1)
k = 1
for n, m, re in Mlist:
n = int(n)
m = int(m)
if (Nlist[n] == 0) & (Nlist[m] == 0):
Nlist[n] = k
if re == "f":
Nlist[m] = k
else:
Nlist[m] = -k
if (Nlist[n] != 0) & (Nlist[m] == 0):
if re == "f":
Nlist[m] = Nlist[n]
else:
Nlist[m] = -Nlist[n]
if (Nlist[n] == 0) & (Nlist[m] != 0):
if re == "f":
Nlist[n] = Nlist[m]
else:
Nlist[n] = -Nlist[m]
if (Nlist[n] != 0) & (Nlist[m] != 0):
if ((Nlist[n] == Nlist[m]) & (re == "e")) | ((Nlist[n] == -Nlist[m]) & (re == "f")):
print(k)
k = 0
break
if abs(Nlist[n]) != abs(Nlist[m]):
temp = Nlist[m]
for i in range(1, N + 1):
if ((Nlist[i] == -temp) & (re == "e")) | ((Nlist[i] == temp) & (re == "f")):
Nlist[i] = Nlist[n]
if ((Nlist[i] == -temp) & (re == "f")) | ((Nlist[i] == temp) & (re == "e")):
Nlist[i] = -Nlist[n]
k += 1
if k != 0:
print("THE SPY DID NOT BETRAY")
def check_unsplit_f(group_A, group_B, unsplit_f):
curr = unsplit_f.copy()
for i in range(len(unsplit_f)):
if (curr[i][0] in group_A and curr[i][1] in group_B) \
or (curr[i][1] in group_A and curr[i][0] in group_B):
return False
elif curr[i][0] in group_A:
group_A.append(curr[i][1])
unsplit_f.remove(curr[i])
elif curr[i][1] in group_A:
group_A.append(curr[i][0])
unsplit_f.remove(curr[i])
elif curr[i][0] in group_B:
group_B.append(curr[i][1])
unsplit_f.remove(curr[i])
elif curr[i][1] in group_B:
group_B.append(curr[i][0])
unsplit_f.remove(curr[i])
return True
def check_unsplit_e(group_A, group_B, unsplit_e):
curr = unsplit_e.copy()
for i in range(len(curr)):
print(curr[i])
if (curr[i][0] in group_A and curr[i][1] in group_A) or \
(curr[i][0] in group_B and curr[i][1] in group_B):
return False
elif curr[i][0] in group_A:
group_B.append(curr[i][1])
unsplit_e.remove(curr[i])
elif curr[i][1] in group_A:
group_B.append(curr[i][0])
unsplit_e.remove(curr[i])
elif curr[i][0] in group_B:
group_A.append(curr[i][1])
unsplit_e.remove(curr[i])
elif curr[i][1] in group_B:
group_A.append(curr[i][0])
unsplit_e.remove(curr[i])
return True
def friend_enermy(M, inp_split):
group_A = []
group_B = []
unsplit_f = []
unsplit_e = []
for i in range(int(M)):
report = inp_split[i+1].split()
if report[2]=='f':
if len(group_A)==0 and len(group_B)==0:
group_A.append(report[0])
group_A.append(report[1])
elif (report[0] in group_A and report[1] in group_B) or \
(report[1] in group_A and report[0] in group_B):
return i+1
elif report[0] in group_A:
group_A.append(report[1])
elif report[1] in group_A:
group_A.append(report[0])
elif report[0] in group_B:
group_B.append(report[1])
elif report[1] in group_B:
group_B.append(report[0])
else:
unsplit_f.append((report[0], report[1]))
else:
if len(group_A) and len(group_B)==0:
group_A.append(report[0])
group_B.append(report[1])
elif (report[0] in group_A and report[1] in group_A) or \
(report[1] in group_B and report[0] in group_B):
return i+1
elif report[0] in group_A:
group_B.append(report[1])
elif report[1] in group_A:
group_B.append(report[0])
elif report[0] in group_B:
group_A.append(report[1])
elif report[1] in group_B:
group_A.append(report[0])
else:
unsplit_e.append((report[0], report[1]))
if check_unsplit_f(group_A, group_B, unsplit_f)==False or \
check_unsplit_e(group_A, group_B, unsplit_e)==False or \
check_unsplit_f(group_A, group_B, unsplit_f)==False:
return i+1
return -1
# inp = """3 3
# 1 2 f
# 2 3 e
# 1 3 f"""
inp = """5 7
1 2 f
3 4 e
4 5 f
2 4 e
1 3 e
1 4 e
5 3 e"""
inp_split = inp.split('\n')
N, M = inp_split[0].split()
ans = friend_enermy(M, inp_split)
if ans == -1:
print('THE SPY DID NOT BETRAY')
else:
print('모순이 발생하는 첫 번째 보고의 번호: ', ans)
JAVA입니다.
package question3.친구냐_적이냐;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Set;
public class Politician {
String name = "";
Hashtable<Politician, Boolean> relationTable = new Hashtable<Politician, Boolean>();
//상대방과의 관계를 표시하는 해시 테이블
//true: 친구, false: 적
boolean updated;
public Politician(String name) {
this.name = name;
this.updated = false; //무한 재귀 방지를 위해 이미 update 했는지 확인
}
boolean update(Politician other, boolean relationship) {
//자신과 상대의 관계 설정, 변경된 관계를 바탕으로 다른 상대와의 관계까지 재귀적으로 갱신
if(updated) {
return true;
}
this.updated = true;
if(relationTable.containsKey(other)) {
if(relationTable.get(other) != relationship) {
//모순
return false;
}
}
else {
relationTable.put(other, relationship);
boolean result = other.update(this, relationship);
if(!result) {
return false;
}
}
Set<Politician> keys = other.relationTable.keySet();
Iterator<Politician> iterator = keys.iterator();
while (iterator.hasNext()) {
Politician politician = (Politician) iterator.next();
if(politician.relationTable.containsKey(other)) {
//상대방과 이미 밝혀진 관계가 있는 정치인에 대해 자신과의 관계 설정
boolean rel = politician.relationTable.get(other);
if(!(politician.name.equals(other.name)) && !politician.name.equals(this.name)) {
boolean result = politician.update(this, (rel) ? relationship : !relationship);
if(!result) {
return false;
}
}
}
}
return true;
}
}
package question3.친구냐_적이냐;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String setting = sc.nextLine();
int polNum = Integer.parseInt(setting.split(" ")[0]);
int comNum = Integer.parseInt(setting.split(" ")[1]);
Politician[] pols = new Politician[polNum];
int err = -1;
for (int i = 0; i < pols.length; i++) {
pols[i] = new Politician(String.valueOf(i + 1));
}
for (int i = 0; i < comNum; i++) {
String[] input = sc.nextLine().split(" ");
int pol1 = Integer.parseInt(input[0]) - 1;
int pol2 = Integer.parseInt(input[1]) - 1;
boolean relationship = input[2].equals("f");
for (Politician politician : pols) {
politician.updated = false;
}
boolean result = pols[pol1].update(pols[pol2], relationship);
if(!result && err == -1) {
err = i + 1;
}
}
System.out.println((err == -1) ? "THE SPY DID NOT BETRAY" : err);
sc.close();
}
}