Problem Solving94 [DFS] 미로 N * M 크기의 2차원 배열로 표현되는 미로 maze가 있다. 미로의 출발점은 maze[0][0] 이고 도착점은 maze[N - 1][M - 1]이라고 하자. maze[i][j]의 값이 1이면 이동이 가능한 지점이고, 값이 0이면 이동이 불가한 지점이다. 미로에서의 이동은 왼쪽, 오른쪽, 위쪽, 아래쪽으로 한 칸씩만 이동이 가능하다. 출발점에서 도착점까지 이동하기 위한 최소 이동횟수를 출력하시오. 단, 탈출 경로가 없는 미로는 주어지지 않는다고 가정해도 된다. Input 첫째 줄에 미로의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 0 또는 1의 값이 주어진다. 출발점과 도착점은 반드시 1로 주어지고, 출발점에서 도착점으로 이동이 가능한 경로는 반드시 하나 이상 존재한다. 4 6 1 0 .. 2022. 12. 15. [DFS] 점프 https://www.acmicpc.net/problem/1890 N * N 숫자판 A에서 개구리가 점프를 한다. 숫자판의 각 셀은 (0, 0) 에서 (n-1, n-1) 이라 한다. 개구리는 각 셀에 적혀 있는 숫자만큼 오른쪽이나 아래쪽으로 점프를 할 수 있다. 개구리는 (0, 0)에서 출발해서 (n-1, n-1)에 도착해야 한다. 정사각형 바깥으로는 점프할 수 없다. N과 A의 각 셀의 숫자가 주어졌을 때, 개구리가 출발점에도 도착점으로 이동 가능한 지를 출력하시오. Input 첫째 줄에 양의 정수 N이 주어진다. 둘째 줄부터 N개의 줄에 A의 각 행의 원소 N개가 한 줄에 하나씩 주어진다. 3 1 2 3 2 3 1 3 2 1 3 1 2 3 2 1 2 3 2 1 Output 첫째 줄에 개구리가 출발점에.. 2022. 12. 15. [DFS] 족보 우리나라에서는 부모와 자식의 관계를 1촌이라고 한다. 따라서, 할아버지와 나는 2촌이 되고, 아버지가 아닌 할아버지의 아들은 3촌이 된다. 주어진 족보에 대해서, 두 사람의 촌수를 출력하시오. 단, 주어지는 족보에서는 부모 중에 한 사람만 표시되고, 친인척이 아닌 사람은 없다고 가정해도 된다. 또한, 촌수가 1,000,000 이상인 입력은 없다고 가정해도 된다. Input 족보에 등장하는 사람은 모두 N명이고, 번호가 1번부터 N번까지 차례대로 부여되어 있다. 족보에 등장하는 부모와 자식 관계는 모두 M개이다. 첫째 줄에 양의 정수 N과 M이 주어진다. 둘째 줄에 촌수를 계산해야 하는 두 사람의 번호 P와 Q가 주어진다. (1 양방향 그래프 생성 family = [[] for _ in range(n+1).. 2022. 12. 15. [DP] 하나가 되고 싶어 어떤 정수 X를 1로 만들고자 한다. 사용할 수 있는 연산은 다음과 같은 세 가지 연산이 있다. 1. X가 3의 배수이면 3으로 나누기 2. X가 2의 배수이면 2로 나누기 3. X에서 1을 빼기 양의 정수 N이 주어졌을 때, 위와 같은 세 가지 연산을 사용해서 1을 만들기 위해 사용해야 하는 연산의 최솟값을 출력하시오. 단, 위의 방법으로 1로 만들 수 없는 경우는 존재하지 않는다고 가정해도 된다. Input 첫째 줄에 양의 정수 N이 주어진다. 1 500000->250000->125000->62500->31250->15625->15624->7812->3906->1953->651->217->216->108->54->27->9->3->1 연산 횟수: 19 2022. 12. 14. 이전 1 ··· 17 18 19 20 21 22 23 24 다음
