본문 바로가기

dfs20

[백준] 21609 상어 중학교 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다. 일반적인 BFS/ DFS 문제보다 신경써서 구현해야 할 부분들이 훨씬 까다로운 문제이므로 과정을 하나하나 잘 살펴보면서 구현하시는 것을 추천드립니다. 풀이 과정 먼저 두 방법으로 풀면서 코드를 두 가지로 작성해보았습니다. 코드①은 구현해야 할 부분들을 그대로 나열식으로 작성한 코드.. 2021. 10. 22.
[백준] 14500 테트로미노 (Python 파이썬) https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 설명 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위.. 2021. 10. 16.
[백준] 12100 2048 (Easy) (Python 파이썬) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 설명 문제에서 주어진 2048 게임을 구현하는 문제이다. 평소의 2048 게임과는 다르게 이동시 새 블록이 추가되지는 않으며 5번 움직였을 때 맵 내의 최대값을 출력하면 된다. 풀이 과정 백트래킹을 이용해 모든 경우의 수에 대해 확인을 해야 하는 브루트포스 문제이다. 움직일 수 있는 방향은 동, 서, 남, 북 4가지 이다. 만약, 동쪽으로 움직인다면 모든 행에 대.. 2021. 10. 14.
[백준] 14888 연산자 끼워넣기 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 주어진 숫자와 연산자로 만들 수 있는 수식의 결과값 중 최대값과 최소값을 구하면 됩니다. 풀이 과정 이 문제는 DFS와 백트래킹을 이용했다. 문제에서 연산에 사용할 숫자(A1,A2...An)와 연산자의 개수(b1, b2, b3, b4)가 주어진다. 연산자는 앞에서 부터 차례대로 더하기, 빼기, 곱하기, 나누기 연산자의 개수를 나타낸.. 2021. 10. 8.
[백준] 2580 스도쿠 (Python 파이썬) https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 설명 스도쿠가 주어졌을 때, 빈 칸을 채워 스도쿠를 완성하는 문제이다. 풀이 과정 문제를 풀기전에, 스도쿠가 무엇인지에 대해 먼저 알아야 한다. 자세한 설명은 위 백준 문제링크에 나와있지만 9 x 9 맵에서 가로(행)에 1~9까지 모든 숫자가 들어가야 하고 세로(열)에도 1~9까지의 모든 숫자가 들어가야하고 3x3 정사각형에도 1~9까지의 모든 숫자가 들어가야 한다. 그래서 맵이 주어졌을 때.. 2021. 10. 8.
[백준] 9663 N-Queen (Python 파이썬) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 풀이 과정 체스판의 퀸은 자신의 줄, 칸, 대각선에 위치한 말을 잡을 수 있다. 이러한 퀸을 N x N의 체스판에 N개 놓을 때 서로 공격할 수 없도록 놓아야 한다. 이 문제는 퀸의 위치를 바꾸어가며 경우의 수를 구하는 DFS+백.. 2021. 10. 7.

티스토리툴바