본문 바로가기

PS78

[BOJ] 9019. DSLR(Python) / BFS www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 처음에는 DFS로 접근했다가 그렇게 해서는 답도 없을 것 같아서 BFS를 떠올렸는데, 결국 혼자 힘으로 못 풀고 다른 사람의 풀이를 봤다ㅠㅠ 사용 알고리즘 : BFS(최단거리 알고리즘) 여러 설명보다 아래 코드를 보면 이해할 수 있을 것이다. 4자리 숫자이므로 일차원 배열 visited를 10000 크기로 만든다. while문을 돌 때마다 현재 temp에 D, S, L, R 연산을 해주며 큐에 (연.. 2021. 3. 25.
[SWEA] 2117. 홈 방범 서비스(Python) swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어렵지 않은 문제이나, 범위 설정하는데 꽤나 애를 먹었다ㅠㅠ # 1시간 10분 소요 두 가지 방법으로 풀어봤다. 첫 번째 방법은, 마름모의 모양을 BFS로 그리는 것이다. 먼저, 지름의 크기 K에 따라 값의 리스트를 미리 만들어놓는다. 맵 내의 모든 위치에서 bfs를 돌리며 중심으로부터 크기가 N+1이 될 때까지 마름모 내에 있는 집의 갯수를 구한다. 마름모의 지름이 1 커질 때마다 큐에 든 갯수만큼만 for문으.. 2021. 3. 25.
[BOJ] 2665. 미로만들기(Python) / BFS www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 고민을 꽤 했던 BFS 최단거리 미로 만들기 문제였다. 벽이 있을 때, 뚫을 수 있되 가장 적게 벽을 뚫고 목적지까지 도달하도록 하는 것이다. visited를 각 위치별로 최댓값 float('inf')으로 초기화한다. maze[nr][nc]가 vistied의 해당 위치를 최솟값으로 갱신할 수 있을 때만 갱신하고 큐에 값을 담는다. 이 때, 빈 공간이라면 벽을 뚫지 않고도 그냥 이동할 수 있으므로 해당 빈 공간의 위치를.. 2021. 3. 25.
[BOJ] 17836. 공주님을 구해라!(Python) / BFS 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 재미있는 BFS 너비우선탐색 문제였다. # 45분 소요 처음에 풀 때 한 번에 답이 나왔지만, 세세한 케이스들을 미처 다 생각하지 못해서 여러 번 제출하며 조건문을 계속 추가했고, 결국 맞았다! 기본적인 BFS 틀에서 내가 고려한 조건은 다음과 같다. 격자에서 이동 중 그람(2)를 만났을 때, 현 위치에서 목적지까지는 거리를 절댓값의 합(minTime)으로 구해 미리 저장해둔다. 목적지까지 정상 도달한 경우도 도중에 그람을 구했든 아니든 반드시! .. 2021. 3. 25.
[BOJ] 2846. 오르막길(Python) www.acmicpc.net/problem/2846 2846번: 오르막길 상근이는 자전거를 타고 등교한다. 자전거 길은 오르막길, 내리막길, 평지로 이루어져 있다. 상근이는 개강 첫 날 자전거를 타고 가면서 일정 거리마다 높이를 측정했다. 상근이는 가장 큰 오르 www.acmicpc.net 브론즈 문제로, 최장 길이를 구하기보다 가장 차이가 많이 나는 오르막길을 구하는 것이다. 이중 for문으로 오르막을 만날 때마다 가장 낮은 부분과 비교해 차이(maxDis)를 갱신해준다. 설명보다 아래 코드를 보는 것이 더 빠른 이해를 도울 것 같다. 파이썬 코드는 다음과 같다. from sys import stdin input = stdin.readline N = int(input()) A = list(map(int.. 2021. 3. 23.
[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.

티스토리툴바