[BOJ-1613] 역사

https://www.acmicpc.net/problem/1613

1613번: 역사

---

 

[방법1] 플로이드 와샬을 이용한 방법

# -*- coding: utf-8 -*-
# 플로이드 와샬..
import sys
class History:
    def __init__(self, n):
        self.n= n
        self.connect=[ [0]*n for _ in range(n)] #인접리스트
        self.visited=None #방문리스트

    def floyd(self):
        for x in range(self.n):
            for y in range(self.n):
                for z in range(self.n):
                    if (x==y) or (y==z) or (x==z):
                        continue
                    else:
                        if self.connect[y][z]==0:
                            #y가 x보다 뒤에 일어난 사건이고(x->y)
                            #x가 z보다 뒤에 일어난 사건이라면(z->x)
                            #y가 z보다 뒤에 일어난 사건이다.(z->x->y )==> (z->y)
                            if (self.connect[y][x]==1) and (self.connect[x][z]==1):
                                self.connect[y][z]=1

                            #y가 x보다 앞에 일어난 사건(y->x)
                            #x가 z보다 앞에 일어난 사건(x->z)
                            #y가 z보다 앞에 일어난 사건이다 (y->x->z)==>(y->z)
                            elif (self.connect[y][x]==-1) and (self.connect[x][z]==-1):
                                self.connect[y][z]=-1
                            
                            

def main():
    #n: 사건의 개수(400이하 자연수)
    #k: 사건의 전후관계 개수(50000이하 자연수)
    n, k= map(int, sys.stdin.readline().split())

    #역사 객체만들기
    h=History(n)

    #인접리스트 만들기
    for _ in range(k):
        front, rear= map(int, sys.stdin.readline().split())
        h.connect[front-1][rear-1]=-1
        h.connect[rear-1][front-1]=1

    h.floyd() #floyd 와샬
    
    #s입력
    s=int(sys.stdin.readline())
    for _ in range(s):
        start, target=map(int,sys.stdin.readline().split())
        h.visited=[False]*n #방문리스트 초기화
        print(h.connect[start-1][target-1])

if __name__=='__main__':
    main() 

---

[방법2] BFS를 이용한 방법

- 풀이

 

- 코드(.py)

import sys
from collections import deque

n,k=0,0
q= deque()
visited=None# 방문리스트
c=None#사건 전후관계를 인접리스트로 나타냄.

def bfs(num):
    global visited, c,n
    target=num
    while q:
        now=q.popleft()     
        #아직 방문하지 않은 상태인가?
        if not visited[now-1]:
            visited[now-1]=True
            
            #c[target][now]!=-1이라면
            if c[target-1][now-1]!=-1:
                c[target-1][now-1]=-1
                c[now-1][target-1]=1

            #아직방문 안한상태이고, now 이전사건인 사건(h)들을 구한다.
            #c[now-1][h-1]=-1
            for h in range(1,n+1):
                if (not visited[h-1]) and (c[now-1][h-1]==-1):
                    q.append(h)

def main():
    global n,k, c, visited
    
    # n: 사건의 개수
    # k: 전후관계의개수
    n,k = map(int, sys.stdin.readline().split())

    #k개의 알고있는 사건의 전후관계를 입력한다.
    c=[ [0]*n for _ in range(n)] 
    for _ in range(k):
        before, after= map(int, sys.stdin.readline().split())
        c[before-1][after-1]=-1 # before->after
        c[after-1][before-1]=1 #after<-before

    for h in range(1,n+1):
        #방문리스트 초기화
        visited=[False]*n
        
        #h와 연결된 사건들중 h이후의 사건들을 큐에 추가 (c[h-1][x-1]==-1)
        for x in range(1,n+1):
            if c[h-1][x-1]==-1:
                q.append(x)
        #bfs실행
        bfs(num=h)

    # s: 사건 전후 관계를 알고 싶은 사건 쌍의 개수
    s= int(sys.stdin.readline())
    for _ in range(s):
        left, right= map(int, sys.stdin.readline().split())
        print(c[left-1][right-1])
        
if __name__=='__main__':
    main()

 

-코드(.java)