https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이 문제도 방향이 8가지로 늘어났다는 점만 제외하고는 아주 기본적인 문제였다. DFS와 BFS 모두 가능하지만 최근에 너무 BFS만 사용한것 같아 이번엔 DFS로 코드를 짜봤다. import sys sys.stdin = open('input.txt', 'r') sys.setrecursionlimit(10**6) dy = (0,1,0,-1,1,1,-1,-1) dx = (1,0,-1,0,-1,1..
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 그래프 탐색 파트의 문제들을 개념부터 차근차근 복기하고 있다. 나이트의 이동은 가장 기본적인 그래프 탐색 문제에서 방향이 8가지로 늘어난것 말고는 다른게 없다. 별다른 제약조건이 없는 상태에서의 최단거리 문제이므로 BFS를 사용했다. 문제 유형에 따라 풀이방법을 나름 정형화 시키고 있다. dx, dy 를 쓴다거나 is_possible의 이름으로 배열 체크 함수를 만든다거나.. 확실히 이정도 수준의 ..
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 간단한 그래프 탐색 문제. 알고리즘 분류에는 플로이드-와샬 이 포함되어 있는데, 간선 사이 가중치가 없고 i에서 j로 가는 경로가 있는지만 체크하면 되는 문제라 일반적인 DFS로 해결하였다. 인접행렬 형태로 받은 간선 정보를 이용하여 간선이 존재하는 기본 좌표를 [start, now] 형태로 stack에 넣어놓고 stack에서 하나씩 pop해 가며 DFS를 수행한다. 문제를 풀어보면서 아직 BFS보다 DFS 구현이 조금 낯선 느낌이 들었다..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 조건도 까다롭지 않고 배열의 입력값 범위도 최대 8이어서 시간복잡도 걱정 없이 부르트포스로 풀면 되겠다고 생각하였다. 문제 풀이에서도 딱히 걸리는건 없었고 최대한 시간와 메모리를 쓰면서 코드를 작성했다. 간단히 짚고 넘어갈 부분은 리스트의 얕은 복사와 깊은 복사 부분 정도인것 같다. 처음에 받은 배열을 계속 깊은 복사하면서 BFS를 시도한다. 주어진 지도에서 3개의 좌표에 벽을 세워야 하는데 이는 배열의..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 겉으로 보면 간단해 보이지만 굉장히 시간초과가 많이 발생하는 문제였다. 처음부터 문제의 조건과 각 풀이방법별 예상 시간 복잡도를 계산해본 후 코드작성에 들어가야 헤매지 않을 수 있는 문제인것 같다. 먼저 문제의 설명과 예시를 보면 가장 먼저 생각나는게 BFS일테고, 각 좌표별로 BFS를 돌려 카운트를 세면 당연히 시간초과가 난다. N by M 행렬이고 N과 M은 각각 10^3..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 그래프 탐색 문제의 또다른 대표 형식인 길찾기 문제이다. 길찾기 문제의 경우 방향값을 미리 코드에 짜두고 for문으로 순회하는 방식의 기법을 항상 기억하고 있어야 한다. 그리고 이 문제의 경우 시작점이 정해져 있고, 도착점까지의 최단거리를 구해야 하기 때문에 한쪽으로 끝까지 들어가는 DFS보다 자신을 기준으로 한레벨씩 나아가는 BFS 방식이 적합하다. 따라서 이 문제의 코드를 짜기 전에 - 길찾기 문제 -> 좌표 활용 - 최단거..
https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 그래프 탐색 문제이다. 처음에는 아무 생각 없이 DFS 방식으로 접근했는데, 문제의 조건을 보니 BFS로 푸는게 가장 옳은 방법인것 같다. 자신의 기준으로 최대 2단계 레벨에 해당하는 친구들의 수를 세서 비교하는 문제라 한쪽으로 끝까지 파고 들어가는 DFS보단 레벨별로 훑어나가는 BFS의 방식이 딱 알맞다. 코드 구성은 BFS에서 최대 2번째 레벨까지만 탐색을 진행하고 카운트를 비교하는 방식. bfs..