https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 휴가 직전은 항상 번아웃이 오는 것 같다. 번아웃이라는 단어로 삶을 대체하기엔 그리 치열하게 살지는 않았던 것 같아서 부끄럽지만, 사람은 핑계의 산물 아니겠는가. 어쨌든 여러 핑계를 뒤로하고 오늘부터 다시 1일 1 알고리즘 체재로 포스팅하지 않을까 싶다. 익숙한 BFS/DFS 문항들은 이제 가닥만 조금 잡히면 구현하는 데에 있어서는 크게 문제 되지 않는 거 같다. # PYTHON CODE (..
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이쪽 문제들은 왜 이렇게 변태 같을까. 진짜 고생했다. 한발 다가가면 두발 멀어지는 놈들이다. 어제 유튜브 알고리즘에 켠 김에 백준 루비 티어 찍는다는 컨셉의 영상도 있더라... 나도 변태 같은 개발자가 되어야겠다. BFS로 접근해야하는 이유는 같은 레벨일 때(걸린 시간이 같을 때)의 케이스들을 따져야 하기 때문이다. # PYTHON CODE (1) from collec..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 무려 7번이나 시간 초과가 발생해서 머리가 터질뻔했다. 답은 의외로 단순한 곳에 있긴 했는데, queue 사용 시, deque모듈을 쓰지 않은 것이 원인이었다. 이 문제가 BFS인 이유는 총 걸린 시간을 구해야 한다는 점과 익은 토마토가 여러군데에 심어져 있다는 점으로 보았을 때, 같은 레벨에 위치한 노드들부터 살피면서 나아가는 탐색이기 때문이다. 처음 추구한 방향은 한 큐가 끝날..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net DFS알고리즘으로 접근했을 때 계속 인덱스 에러가 나서 고생했다. # PYTHON CODE (1) - DFS import sys sys.setrecursionlimit(2500) t = int(sys.stdin.readline()) def dfs(a, b): if a = n or b = m: return False if tree[a][b] == 1: tree[a][b] = ..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 전형적인 DFS/BFS 문제는 풀기 좀 쉽다고 들었는데, 무슨 의미인지 알 것 같다. # PYTHON CODE (1) - BFS import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) tree = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, sys.stdin.read..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 분류는 BFS지만 DFS로도 구현할 수 있는 문항이다. 이전 문제와 마찬가지로 전형적인 BFS/DFS 문제라는데 아직 어려운 것 같다.. 코드 또한 상당히 비슷하긴 하다. # PYTHON CODE(1) - BFS import sys def bfs(tree, a, b): cnt = 1 # 아래 for문이 실행할 때 tree값이 1일때부터 확인하므로 0이 아니라 1로 설정. queue = deque()..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 어제 문제 풀 때만 해도 아 이런 느낌이구나 하는 감이 왔었는데, 문제가 조금만 달라지면 그 느낌도 초기화가 되나 보다. 경건한 마음으로 구글링의 도움을 받았다. 100% 이해 완료하긴 했는데, 뭔가 비효율적인 것 같으면서도 거의 모든 풀이가 단일화되어 있는 걸 보면 이게 가장 좋은 풀이인가 싶은 의문이 든다. 풀이가 굉장히 알고리즘스러운데, dx, dy의 설정으로 상하좌우의 경우를 생각해주는 건 진짜 괜찮은 방법인 것 같다. ..
