본문 바로가기

BOJ67

[BOJ] 13023. ABCDE(Python) / DFS www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 깔끔한 DFS 문제였다. input 받으면서 정점별로 갈 수 있는 정점의 정보를 딕셔너리에 담는다. 전역변수 flag를 두어 depth가 4이상 되면 1로 바꿔주며 return하여 더이상 진행하지 않는다. 모든 정점에서 start할 수 있다. visited로 아직 방문하지 않는 곳에 방문체크하며 다음 재귀로 넘어간다. 재귀 풀려 나올 땐 방문체크한 것을 0으로 돌려 놓는다. flag가 1이면 1, 0이면 0을 출력한다. 파이썬 코드는 다음과 같다. import sys input = sys.stdin.readline .. 2021. 3. 23.
[BOJ] 6087. 레이저 통신(Python) / BFS www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 연속으로 BFS 최단거리 문제를 풀었다. 문제를 처음 접했을 때 이전의 로봇 문제처럼 맵을 방향별로 만들어줘야겠다는 생각을 했는데, 조금 더 생각해보니 그렇게까지 할 필요는 없을 것 같고, 머릿 속으로 BFS 이차원 맵을 어떻게 채울지 생각했다. 초기 check 맵을 최댓값 float('inf')으로 채워 놓는다. 시작 위치에서 4방향으로 쭉쭉 직진으로 벽이나 격자 밖으로 나갈 때까지 그려주고, 그 다.. 2021. 3. 22.
[BOJ] 1726. 로봇(Python) / BFS www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net BFS 최단거리 문제다. 처음에 문제 봤을 때 어떻게 풀어야할지 좀 막막했는데 여러 솔루션들을 보고 아이디어를 얻었고, 특히, 뚱이가 코드를 보내줘서 완벽히 이해할 수 있었다. 내 스타일대로 다시 풀어봤다. 이 문제에서 포인트는 visited를 맵의 크기대로 그리되, 각 위치별로 4방향(동서남북) 정보를 담을 수 있도록 * 4 해주는 것! 큐에 위치와 방향, 그리고 cnt값을 담았다. 해당 정보를 visited에 표시하며.. 2021. 3. 22.
[BOJ] 1149. RGB거리(Python) / DP www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 실버 1 문제라 간단한 DFS로 Brute Force(완전탐색)으로 풀릴 줄 알았는데, 47%에서 시간초과 나더라.. # 소요시간 20분 DFS 완전탐색으로 접근한 파이썬 코드는 다음과 같다.(47%에서 실패한 코드) from sys import stdin input = stdin.readline def dfs(depth, temp): global MIN if temp > MIN: # 가지.. 2021. 3. 17.
[BOJ] 6603. 로또(Python) / DFS www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 간단한 DFS로 조합(Combination)을 구현한 문제다. # 소요시간 12분 lottos에 담긴 숫자들 중 순서를 고려하지 않고 6개를 뽑아 차례로 출력한다. 이미 배열은 오름차순으로 되어있기 때문에 그대로 이미 뽑혔는지 확인해주며 뽑히지 않았다면 뽑은 표시 후 다음 자릿수에서 탐색한다. depth == 6이 될 때 출력한다. 파이썬 코드는 다음과 같다. import sys input = sys.. 2021. 3. 17.
[BOJ] 13305. 주유소(Python) / Greedy www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 이해하는 건 금방이었다. 그리디(Greedy) 알고리즘으로 접근했다. 그리디하게 for문으로 1번 인덱스부터 현재 위치에서의 주유비와 이전의 주유비와 비교, 최솟값으로 갱신한다. 최소 주유비로 거리를 곱한 값을 전체 가격 total 변수에 더해준다. 늘 느끼듯 Greedy나 DP는 발상이 힘들지, 코드는 짧다. 파이썬 코드는 다음과 같다. import sys input = sys.stdin... 2021. 3. 12.

티스토리툴바