AtCoder Beginner Contest 405 대충 복기(BFS, 최단경로, 경우의수, 팩토리얼 모듈로 역원)

1. D번

 

D - Escape Route

D - Escape Route

 

 

2차원 배열이 주어질때, 각 위치에서 탈출구 E번까지 가는 최단 경로를 표시해야하는 문제

 

#은 이동불가능 지역이므로 표시하지 않는다.

 

..E

...이라고 한다면?

 

>>E

>>^ 이런식으로 될 것이다.

 

혹은 정답이 여러개일 수 있는데

 

>>E^>^도 정답이 될듯?

 

각각의 지점에서 E까지 가는 최단 경로를 어떻게 찾는다고 하더라도 표시를 어떻게 해야하지?

 

각각의 지점이 1000*1000개인데 이걸 언제 다하냐?

 

그러면 반대로 생각해서 E에서 출발해서 각 지점까지 BFS로 그래프 탐색을 한다면..?

 

탐색하면서 각 지점에 이동 방향 표시를 해줌

 

그러면 그 이동방향 표시는 E에서 각 지점까지의 최단 경로 표시가 된다

 

그리고 이 이동방향 표시를 다시 반대로 바꿔주면 된다

 

처음에 모든 지점을 탐색해서 E의 좌표를 모두 큐에 넣고 BFS를 수행하면서 각 지점까지 이동방향 표시를 해주고,

 

마지막에 다시 모든 지점을 탐색해서 이동방향 표시가 된 지점을 반대 방향으로 바꿔줌

 

>은 <으로 ^은 V으로 

 

from collections import deque

h,w = map(int,input().split())

S = [list(input()) for _ in range(h)]

queue = deque([])
visited = [[0]*w for _ in range(h)]

for y in range(h):
    
    for x in range(w):
        
        if S[y][x] == 'E':
            
            queue.append((x,y))
            visited[y][x] = 1

delta = [[0,1],[1,0],[0,-1],[-1,0]]
char = ['v','>','^','<']
reverse = ['^','<','v','>']

while queue:
    
    x,y = queue.popleft()

    for i in range(4):
        
        a,b = delta[i]

        dx = x + a
        dy = y + b

        if dx >= 0 and dx <= w-1 and dy >= 0 and dy <= h-1 and S[dy][dx] == '.' and visited[dy][dx] == 0:
            
            visited[dy][dx] = 1
            queue.append((dx,dy))
            S[dy][dx] = char[i]
    
for y in range(h):
    
    for x in range(w):
        
        for i in range(4):
            
            if S[y][x] == char[i]:
                
                S[y][x] = reverse[i]
                break

for row in S:
    
    print(''.join(row))

 

 

혹은 BFS하면서, 아예 반대방향으로 표시해둔다면, 마지막에 다시 방향을 바꿀 필요는 없겠지

 

from collections import deque

h,w = map(int,input().split())

S = [list(input()) for _ in range(h)]

queue = deque([])
visited = [[0]*w for _ in range(h)]

for y in range(h):
    
    for x in range(w):
        
        if S[y][x] == 'E':
            
            queue.append((x,y))
            visited[y][x] = 1

delta = [[0,1],[1,0],[0,-1],[-1,0]]
reverse = ['^','<','v','>']

while queue:
    
    x,y = queue.popleft()

    for i in range(4):
        
        a,b = delta[i]

        dx = x + a
        dy = y + b

        if dx >= 0 and dx <= w-1 and dy >= 0 and dy <= h-1 and S[dy][dx] == '.' and visited[dy][dx] == 0:
            
            visited[dy][dx] = 1
            queue.append((dx,dy))
            S[dy][dx] = reverse[i]

for row in S:
    
    print(''.join(row))

 

 

 

2. E번

 

E - Fruit Lineup

E - Fruit Lineup

 

 

사과, 오렌지, 바나나, 포도가 a,b,c,d개 있다.

 

이들을 일렬로 배열하고자 하는데, 다음과 같은 조건을 만족해야한다.

 

모든 사과는 모든 바나나의 왼편에 있어야한다.

 

모든 사과는 모든 포도의 왼편에 있어야한다.

 

모든 오렌지는 모든 포도의 왼편에 있어야한다.

 

사과, 오렌지, 바나나, 포도는 각각 구별할 수 없는, 동일한 과일들 이라고 할때, 조건을 만족하면서 배열하는 경우의 수는?

 

----------------------------------------------------------------------------------------------------------------------------

 

포도 왼쪽에 사과 오렌지가 있어야하기 때문에

 

(사과, 오렌지) ||||| (포도)

 

이런 형태가 되어야한다.

 

이 상태에서 바나나의 배치가 중요한데, 가장 왼쪽에 있는 포도를 기준으로

 

그 왼쪽에 i = 0,1,2,...,C개의 바나나가 있다고 하자.

 

(사과 A개, 오렌지 B개, i개의 바나나) (포도) (포도 D-1개,바나나 C-i개) 이런 형태

 

 

그러면 (사과 A개, 오렌지 B개, i개의 바나나)을 일렬로 배열하는 경우의 수는?

 

여기서 사과, 오렌지, 바나나 각각은 구별할 수 없는 과일이라는 점에 주목해야한다.

 

그러니까 각각은 순열해봤자 동일하다는 거

 

그리고 모든 사과는 바나나의 왼편에 있어야한다는거

 

그러면 A개의 사과와 i개의 바나나를 일단 배열하고 그 사이사이 빈칸(빨간, 주황부분)에 오렌지 B개를 넣으면 된다.

 

 

 

그러면 빨간색 표시 A개, 주황색 표시 i+1개라서 사이사이가 A+i+1개인데, 여기에 B개의 오렌지를 넣는다면?

 

A+i+1개의 자리 중 B개의 자리를 선택해 각각을 집어넣으면 되니까 A+i+1 C B가지?

 

그건 아니고

 

1자리에 여러개의 오렌지를 넣어도 된다

 

이렇게도 되잖아

 

 

 

그래서 A+i+1개중 B개의 자리를 중복해서 선택하는 중복조합 A+i+1HB가지

 

nHr = n+r-1Cn-1

 

n명 중 k명을 중복해서 선택하는 중복조합의 수 이해하기

n명 중 k명을 중복해서 선택하는 중복조합의 수 이해하기

 

 

이는 A+i+1+B-1 C  A+i가지와 같다.

 

그러면 두번째로

 

(사과 A개, 오렌지 B개, i개의 바나나) (포도) (포도 D-1개,바나나 C-i개) 이런 형태

 

포도 왼편은 구했으니까 오른편 (포도 D-1개, 바나나 C-i개)를 배열하는 방법의 수는?

 

포도와 바나나는 자유롭게 배열할 수 있으므로, 포도 D-1개, 바나나 C-i개를 일렬로 배열하는 복수 순열의 개수와 같다.

 

이는 (C-i+D-1)! / ((C-i)!(D-1)!)가지

 

 

팩토리얼(factorial)의 소수 모듈로 곱셈의 역원(modulo inverse)을 구하는 기본적인 테크닉

팩토리얼(factorial)의 소수 모듈로 곱셈의 역원(modulo inverse)을 구하는 기본적인 테크닉

 

 

팩토리얼의 소수 998244353 모듈로 곱셈의 역원과 팩토리얼 모듈로 값을 모두 미리 구해놓는다면 빠르게 구할 수 있다

 

 

a,b,c,d = map(int,input().split())

mod = 998244353

#팩토리얼, 팩토리얼 역원 모두 구해놓기
n = a+b+c+d

factorial = [0]*(n+1)
factorial[0] = 1

for i in range(1,n+1):
    
    factorial[i] = factorial[i-1]*i
    factorial[i] %= mod 

factorial_inverse = [0]*(n+1)
factorial_inverse[n] = pow(factorial[n], mod-2, mod)

for i in range(n,0,-1):

    factorial_inverse[i-1] = factorial_inverse[i] * i
    factorial_inverse[i-1] %= mod


#a+b+iCb * (c-i+d-1)!/(d-1)!(c-i)!을 i = 0,1,,...,c에 대해 모두 합해줌
count = 0

for i in range(c+1):
    
    v1 = factorial[a+b+i]*factorial_inverse[b]*factorial_inverse[a+i]
    v1 %= mod

    v2 = factorial[c-i+d-1]*factorial_inverse[d-1]*factorial_inverse[c-i]
    v2 %= mod

    count += v1*v2
    count %= mod

print(count)