본문 바로가기

Algorithm

 (130)
[Python] 백준 7562번 : 나이트의 이동 (S2) - DFS&BFS단계별10 #문제 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net #풀이 & 학습한 내용 "나이트를 목적지까지 이동시키는 최소이동횟수"를 구하는 문제입니다. bfs로 최소경로를 구하면 답을 구할 수 있으며, visited 리스트를 따로 선언해주어 이미 방문한 곳은 큐에 넣지 않도록 구성해야 시간초과에 걸리지 않습니다. #소스코드 from collections import deque #큐 사용하기 위해 dx=[2,2,-2,-2,1,1,-1,-1] dy=[1,-1,1,-1,..
[Python] 백준 2206번 : 벽 부수고 이동하기 (G4) - DFS&BFS단계별9 #문제 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net #풀이 & 학습한 내용 "현재 상태"를 정점으로 표현하여 그래프를 만들고 최단거리를 구하는 문제입니다. bfs로 최단거리를 구하는 미로찾기 문제에서, 벽을 하나 부술 수 있다는 옵션이 추가되었습니다. 이때 방문여부를 판단하는 visited를 벽을 부순 케이스와 벽을 안 부순 케이스로 나누어 따로 관리해주어야 하는 것이 이 문제의 핵심입니다. velog.io/@jengyoung/b..
[Python] 백준 1697번 : 숨바꼭질 (S1) - DFS&BFS단계별8 #문제 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net #풀이 & 학습한 내용 "또 다른 BFS 최단거리 연습문제"입니다. BFS를 통해 가장 최소횟수를 구해주며, 현재위치의 범위와 방문여부로 중복을 제거해야 메모리초과에 걸리지 않고 문제를 해결할 수 있습니다. #소스코드 from collections import deque #큐 사용하기 위해 def bfs(q): while q: #K위치에 도달할 때까지 계속 반복(도달불가능한 경..
[Python] 백준 7569번 : 토마토 (S1) - DFS&BFS단계별7 #문제 www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net #풀이 & 학습한 내용 supremo7.tistory.com/207?category=874979의 3차원 버전 문제입니다. 여기서 정말 주의해야 될 점은 Z방향으로 리스트를 참조할 때 tomatoes[위아래][가로][세로]로 Z값이 맨 앞에 온다는 점입니다. 이 부분을 잘 생각하면서 코드를 짜야 합니다. #소스코드 from collections import deque #큐 사용하기..
[Python] 백준 7576번 : 토마토 (S1) - DFS&BFS단계별6 #문제 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net #풀이 & 학습한 내용 "BFS로 토마토를 익히는 문제"입니다. bfs를 시작하기 전에 익은 토마토들을 먼저 모두 큐에 넣고 수행하는 것이 핵심입니다. 그리고 bfs가 끝나고 큐가 모두 비워지면 익을 수 있는 토마토는 모두 익은 것이므로, bfs이후에 안익은 토마토가 있는 지 확인하여 모두 익히는 것이 불가능한지 여부를 확인해주면 됩니다. #소스코드 from collections impo..
[Python] 백준 14889번 : 스타트와 링크 (S3) #문제 www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net #풀이 & 학습한 내용 pypy3는 python3에 비해 빠르지만 메모리를 많이 소요합니다. 이번 코드의 경우에는 시간초과가 우려되었지만, PyPy3와 Python3 모두 통과되었습니다. 또한, itertools의 combinations를 통해서 문제를 편하게 해결할 수 있었습니다. 리스트끼리 덧셈은 되지만, 뺄셈은 되지 않아서 [x for x in list(range(N)) if x not in team1]와 같이 적어 뺄..
[Python] 백준 14501번 : 퇴사 (S4) #문제 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net #풀이 & 학습한 내용 시작과 종료일이 있고, 각각의 수익이 다른 상담들 중에서 총 수익을 최대화하는 문제입니다. 종료일 기준으로 오름차순 정렬한 후에, dp[k]를 "k일까지의 최대이익"으로 정의하여 dp리스트를 앞에서부터 채워나갑니다. 그리고 dp[N]이 N일까지의 최대이익이므로 정답으로 출력합니다. #소스코드 N=int(input()) consults=[] #상담들 저장하는 리스트 dp=[0]*(N+1) #★dp[k]: k일까지의 최대이익 for i in range(N): one_consult=[i+1]+list(map(int,inpu..
[Python] 백준 2178번 : 미로 탐색 (S1) - DFS&BFS단계별5 #문제 www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #풀이 & 학습한 내용 "BFS의 특징은 각 정점을 최단경로로 방문한다는 것입니다. 이 점을 활용해 최단거리를 구해 보는 문제"입니다. 그저 평소의 bfs에서 최단경로를 세는 리스트만 추가해주면 해결되는 문제였습니다. 방문처리를 꼭 해주어 무한루프를 도는 일이 없게 해야 합니다. #소스코드(22번 쨰 줄 주목) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

티스토리툴바