본문 바로가기
반응형

Problem Solving/DFS, BFS26

[DFS / 파이썬] 백준 16724번 : 피리 부는 사나이 / 골드 2 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net x_lim, y_lim = map(int, input().split()) table = [] for _ in range(x_lim): table.append([x for x in input()]) group = [[-1 for _ in range(y_lim)] for _ in range(x_lim)] direction = ['L', 'R', 'U', 'D'] d.. 2022. 4. 4.
[백트래킹 / 파이썬] 백준 15684번 : 사다리 조작 / 골드 4 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 처음엔 헉..하고 당황했으나 역시 차근차근 생각하면 실마리가 풀린다. 백트래킹으로 접근했고, 필요한 사다리의 최소 개수를 찾으라는 것에서 약간 멈칫한 이유는 백트래킹은 기본적으로 dfs로 탐색이 이루어지는데 최소 개수면 bfs로 해야 하나? 라는 생각이 들었기 때문이다. 하지만 사다리 개수는 while문을 통해 제어를 해주면 되고, 그 정해진 사다리 개수 내에서 원래 하던대로 dfs로 백트래킹을.. 2022. 3. 5.
[BFS / 파이썬] 백준 9019번 : DSLR / 골드 4 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net import collections def op_d(n): return (2*n) % 10000 def op_s(n): if n == 0: return 9999 else: return n-1 def op_l(n): d1, d2, d3, d4 = n_to_digit(n) return digit_to_n(d2, d3, d4, d1) def op_r(n): d1, d2, d3, d4 = n_.. 2022. 3. 2.
[BFS] 백준 7569번 : 토마토 / 골드 5 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net import collections m, n, h = map(int, input().split()) box = [] left = 0 q = collections.deque() for z in range(h): table = [] for y in range(n): row = list(map(int, input().split())) for x in range(len(row)): .. 2022. 2. 24.
[백트래킹] 백준 9663번: N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹으로 잘 알려진 문제다. n = int(input()) graph = [[0 for _ in range(n)] for _ in range(n)] global cnt cnt = 0 def isPossible(x, y, num): for i in range(n): # row and col graph[i][y] += num # diagonal for i in range(n): if 0 2021. 9. 15.
[DFS, BFS/파이썬] 백조의 호수 / 플래티넘 5 ** https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 처음엔 많이 풀어본 유형인듯 했으나 쉽게 풀리지 않았다. 시간 제한이 빡셌다. 풀이 방식: 우선 백조가 만날 수 있는 지 여부는 bfs 탐색을 이용한다. 이때 q 리스트와 next_q 리스트를 사용했다. 37~51 일반적인 bfs처럼 q에서 원소하나씩을 빼서 조사를 하되, 빙판인 곳을 만나면('X') next_q에 이 좌표를 추가한다. 왜냐면 이 빙판은 어차피 다음 턴.. 2021. 9. 11.
반응형

티스토리툴바