본문 바로가기

Problem Solving96

[Backtracking] BOJ 15650 N과 M(2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #2022.12.29 import sys input=sys.stdin.readline n, m = map(int, input().split()) answer = [] def backtracking(start): if len(answer)==m: print(' '.join(map(str, answer))) for i in range(start, n+1): if i not in answer: ans.. 2022. 12. 30.
[Back Tracking] 복면산 https://www.acmicpc.net/problem/15811 import sys input=sys.stdin.readline from itertools import permutations cnt=0 def to_int(rev, DICT): value=0 for i in range(len(rev)): value+=DICT[rev[i]]*(10**i) return value def promising(i, n, D, s1, s2, s3): if i==0: return True a=to_int(s1, D) b=to_int(s2, D) c=to_int(s3, D) M=10**i return (a+b)%M == c%M def backtrack(i, n, D, r1, r2, r3): global cnt if .. 2022. 12. 15.
[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.

티스토리툴바