[백준] 1326번: 폴짝폴짝

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

난이도: 실버2

▶ 문제 탐색하기

재귀함수를 이용해서 최소한 점프할 수 있는 방법을 탐색한다. 

 

◇ 입력

1. 징검다리 개수 N (1~10,000 정수)
2. N개의 징검다리에 쓰여진 자연수 ---> arr =[]
3. 시작 a번째 징검다리, 도착 b번째 징검다리

 ◇ 원하는 출력 조건

1.  a번 징검다리에서 b번 징검다리로 최소 몇 번 점프해서 갈 수 있는지? 
2. 만약 갈 수 없다면 -1 출력  

가능한 시간복잡도 

 

알고리즘 선택

- BFS 알고리즘 사

▶ 코드 설계하기

 1. 가장 먼저, arr[ a-1 ] 시작점 값과 뛰어야하는 전체 거리 ( b-a )를 찾는다. 

 

 2. 만약 전체 거리가 시작점 값으로 나누어 떨어진다면 한 번에 뛰어 건널 수 있다.

①  if (b-a) % arr[a-1] == 0,  return 1

②  else: 나머지가 생긴가면? 극한의 상황을 생각해야하는데

 

 3. a에서 b로 갈 수 없는 경우? return -1

① 시작점 값 arr[ a-1 ] 이 전체 거리 ( b-a ) 보다 클 때

② if (b-a) % arr[a-1] == 0,  return 1

 

▶ 회차별 수정사항

• 개구리는 앞으로만 움직인다고 생각했는데 그런 조건은 적혀있지 않았다. 앞뒤로 움직일 수 있는 개구리였다
•  

▶ 정답 코드

# 5*5 빙고 array로 입력받고 사회자가 부르는 번호
array, num = [], []
for i in range(5):
  arr = list(map(int, input().split()))
  array.append(arr)
for j in range(5):
  num.extend(map(int, input().split()))
  
# marked를 통해서 부르는 번호를 표시함
marked = [[False]*5 for _ in range(5)]
def bingo_check(marked):
  for _ in range(5):
    cnt = 0
    for i in marked:
      if all(i):
        cnt += 1
    for j in range(5):
      if all(marked[i][j] for i in range(5)):
        cnt += 1
    if all(marked[k][k] for k in range(5)):
      cnt += 1
    if all(marked[k][4-k] for k in range(5)):
      cnt += 1
    return cnt >= 3
# True로 부르는 숫자를 하나씩 지워감
for n in num:
    found = False  
    for i, row in enumerate(array):
        if n in row:
            j = row.index(n) 
            marked[i][j] = True  
            if bingo_check(marked):
                print(num.index(n) + 1) # 몇 번째 숫자로 바꿔준다.
                found = True  
                break  
    if found:
        break

 

▶ 추가 풀이