https://www.acmicpc.net/problem/15684
문제 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.
초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.
위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다.
사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다.
위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다.
사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.
이미지는 몇 개는 표시가 안되는데 마찬가지로 링크에 들어가시면 됩니다.
참고 코드: https://suri78.tistory.com/212
문제를 풀다보면 어떤 최적화된 값을 찾거나 휴리스틱하게 찾아가는 것과는 달리 완전탐색으로 푸는 경우가 상당히 많은거 같습니다. 그러다보니 코테를 준비하면 C++을 권하는게 괜히 있는게 아니지요 속도면에서 무식하게 짜도 통과할 수 있다는 거는 굉장힌 이득이니….. 그래도 백준은 pypy3를 지원하니 이거를 믿고 해봅시다.
1
2
3
4
5
6
from sys import exit
n, m, h = map(int, input().split())
if m == 0:
print(0)
exit()
첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. 그리고 i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다.
여기서 M이 0이면 더 가로선을 추가할 수 없으니 시작하자마자 m이 0이라면 그냥 0을 출력해버리고 exit로 코드를 종료합시다.
1
2
3
4
bridge = [[False] * n for _ in range(h)]
for _ in range(m):
a, b = map(int, input().split())
bridge[a-1][b-1] = True
방문하는 노드를 체크를 하고 (결국 사다리라고 해도 2차원 매트릭스이니)
입력 조건: 가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다.
조건에 따라서 사다리가 놓인 곳은 True라고 체크를 합시다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bf(cnt, x, y):
global ans
if check():
ans = min(ans, cnt)
return
elif cnt == 3 or ans <= cnt:
return
for i in range(x, h):
k = y if i == x else 0
for j in range(k, n-1):
if not bridge[i][j] and not bridge[i][j+1]:
bridge[i][j] = True
bf(cnt+1, i, j+2)
bridge[i][j] = False
먼저 bfs함수를 먼저 봅시다. 일단 우리가 구하는 답(최소한으로 놓을 수 있는 가로의 개수) ans를 둡시다.
바로 밑에 체크 함수가 나오는데 일단 이거는 나중에 다시 보고 먼저 elif부터 보겠습니다. 조건에서 불가능하거나 답이 3을 넘어가면 -1로 출력을 하라고 되어 있습니다. 그래서 이때도 조건을 확인합니다.
그다음 for문을 봅시다.
우리는 맨 처음 조건에 따라서 0,0에서 시작을 한다고 했습니다. 그러면 범위는 0부터 h(선을 놓을 수 있는 개수)까지 반복을 합니다. 그리고 이때 k는 x가 끝에 다다르지 않는다면(더이상 놓을수 없을때) y값을 넣게 됩니다.
그리고 k부터 n-1까지인데 다시 설명 하자면 먼저 k는 몇번째 줄에 놓을지 선택을 하고(첫번째 for문) 그다음 몇 번째 칸에 놓을지 (두번째 for문)을 결정을 합니다. 그리고 해당 브릿지가 False가 아닐때(가로로 넣을 수 있을때) 해당 브릿지에다가 넣어두고
그다음 bfs함수로 재귀로 부르는데 이때 count는 1 증가시키고 y도 2를 증가를 시킵니다. 이때 가로선이 – 이어서 붙으면 안되기 때문
1
2
3
4
5
6
7
8
9
10
11
def check():
for start in range(n):
k = start
for i in range(h):
if bridge[i][k]:
k += 1
elif k > 0 and bridge[i][k-1]:
k -= 1
if start != k:
return False
return True
그러면 check를 한번 봅시다. check는 사다리를 태워서 어디가나 확인하는 함수입니다.
for문은 1번부터 N번 세로선(열)까지 검사를 하게되고 처음부터 start를 합니다.
그리고 가로를 하나하나 이동하면서 해당 브릿지에 다리가 이미 존재한다면 k+=1로 한칸 옆으로 이동을 합니다.
만약 가로선이 왼쪽에 존재한다면 k-=1 왼쪽으로 한칸 이동합니다.
그렇게 가장 하단까지 왔는데 k가 start랑 같지 않다면 문제가 발생했습니다. 원래 목표하던 목적지에 도달하지 못했다는 의미입니다. 그러니 False를 반환하고 만약 출발한 곳과 도달한 직선이 같다면 True를 반환합니다.
1
2
3
ans = 4
bf(0, 0, 0)
print(ans if ans < 4 else -1)
ans는 4로 초기화해서 시작을 합니다. 어차피 3보다 크거나 불가능하다면 -1을 출력하거든요
마지막 출력문에 저렇게 조건문을 삽입할 수 있습니다. ans<4를 만족한다면 ans를 출력하고 아니라면 else -1을 출력합니다.
Comments powered by Disqus.