본문 바로가기

PYTHON71

[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.
[SWEA] 2382. 미생물 격리(Python) / Simulation swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 47분 소요 사실 이 문제도 5번? 정도 푼 문제라서 풀 때마다 Pass까지의 시간이 단축되는 것 같다 ㅋㅋㅋ 특별히 사용한 알고리즘은 없고, 이차원 배열과 딕셔너리 자료구조를 이용했다. 겉으로는 Simulation이지만, 일일이 맵을 만들 필요는 없어 보였고, 이차원 배열을 만들어 M시간만큼 이차원 배열에 들어있는 미생물의 정보(위치, 미생물갯수, 방향)를 변화시키는 방식으로 접근했다. 그냥 생각나는대로 직.. 2021. 3. 23.

티스토리툴바