링크 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 소요시간: 50분 36초 설계하기(접근방법) 1. 입력받기 배열을 입력받는다 2. 구현하기 이 문제는 각각의 graph에 대해서 여러번 bfs를 돌려야하는 문제다 물의 수위가 0일 때부터 배열의 최대값까지 전부 돌려보고 그 중에 안전한 영역이 언제 최대인지 max 값을 저장하면 된다 3. 출력하기 max값을 출력한다 코드(출력) from collections import deque impo..
링크 : https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제 소요시간: 42분 2초 설계하기(접근방법) 1. 입력받기 문제의 요구사항을 입력받는다 2. 구현하기 이 문제의 핵심은 평상시 풀던 문제와는 좌표설정이 다르다는 점이다 dx = [0, 0, 1, -1] dy = [1, -1, 0 ,0] 이었던 1칸씩 탐지하던 것을 나이트의 이동방식대로 바꾸면 쉽게 풀 수 있다 3. 출력하기 목표 좌표로 가는 최단거리를 구한다 코드(출력) from col..
링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 소요시간: 35분 실패 설계하기(접근방법) 1. 입력받기 행렬을 입력받는다 2. 구현하기 bfs로 풀면 쉬운 문제였다 dfs로 풀었다가 최저 해를 보장할 수 없는 상황이 발생해서 틀렸다 bfs를 구현해서 가장 최단거리를 계산한다 3. 출력하기 최단거리를 계산한다 코드(출력) from collections import deque def bfs (x,y): dx = [1, -1, 0, 0] dy = [0 ,0 ,-1,..
링크 : https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 소요시간: 57분 15초(디버깅 35분) 설계하기(접근방법) 1. 입력받기 행열을 입력받는다 2. 구현하기 간단한 bfs, dfs 문제이다. bfs 함수를 선언하고, 배추가 없을 때까지 배추밭을 순회할 때마다 cnt를 해준다 3. 출력하기 cnt를 출력한다 코드(출력) from collections import deque def bfs(x,y): dx = [0 ,0, 1, -1] dy = [1,..
링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 소요시간: 연습 설계하기(접근방법) 1. 입력받기 정점, 간선, 시작 정점을 입력받는다 2. 구현하기 dfs와 bfs를 각각 구현한다 2번에 걸쳐서 돌릴 것이기 때문에 각각 visited를 선언해준다 또한 입력 조건에 간선을 순서대로 준다는 말이 없고 정점을 작은 순서대로 방문한다고 했으니 for i in graph: i.sort()를 통해 정렬..
링크 : https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 소요시간: 연습 설계하기(접근방법) 1. 입력받기 요구사항을 입력받는다 2. 구현하기 사람의 번호를 넣으면 촌수를 계산해주는 bfs를 구현할 것이기 때문에 bfs(number) 방식으로 코드를 짜준다 인접리스트 방식으로 graph를 선언해주고 해당 num 의 bfs를 계산했을 때, 각각의 노드에 대한 가중치를 넣어주어야 하기 때문에 visited = [0] * (..
링크 : https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 소요시간: 연습문제 설계하기(접근방법) 1. 입력받기 행, 열의 개수와 이차원 배열을 입력받는다 2. 구현하기 BFS 구현을 연습해본다 3. 출력하기 코드(출력) from collections import deque n, m = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] visi..
링크 : https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 문제 소요시간: 14분 45초 설계하기(접근방법) 1. 입력받기 입력받을 문자가 많으니 sys를 통해 입력받는다 2. 구현하기 입력과, 테스트의 수가 4억개까지 늘어날 수 있으니 시간초과에 주의해야 하는 문제다 단어의 중복을 허용하지 않으니 딕셔너리로 구현하여 탐색한다면 시간을 많이 줄일 수 있다 먼저 입력받은 메모장을 모두 딕셔너리에 넣어준 후 dict..
