www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 1. 보물 -> 육지 사이의 최장거리이므로 지도(m)을 입력받고 지도에 있는 모든 육지좌표를 land배열에 저장한다. 2. bfs함수: visited배열초기화, dist배열 0으로 초기화, (i, j) 시작지점에 대해 deque에 넣고 bfs를 돌린다. 만약 상하좌우 칸에 방문하지 않았고, 그 칸이 육지라면 거리를 1증가시킨다. 최종적으로 거리의 최댓값을 return (27번째 줄 코드는 2차원 배열에서 최댓값을 ..
programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 백준에서 많이 풀어본 그래프 문제들과 비슷하다. 처음에 DFS로 풀어보려다 실패하고 BFS로 풀었다. from collections import deque def solution(n, edge): graph = [[] for _ in range(n+1)] dist = [0] * (n+1) visited = [False] * (n+1) q = deque() q.append(1) visited[1] = True for i in edge: graph[..
www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net N이 100이하이므로 O(N^3)인 플로이드-와샬 알고리즘을 사용해도 통과가 될 것 같아서 풀어보았다. 1. M개 만큼 a와 b를 입력받고 a와 b사이의 거리를 1로 cost배열에 넣어준다. 2. 플로이드-와샬 알고리즘을 통해 각 건물 사이의 거리를 구해준다. 3. 브루트포스 방식으로 치킨집이 1번,2번일 때 부터 1번,3번 ... N-1번,N번까지일 때 모든 도시에서의 왕복 시간..
www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이런 유형의 문제를 처음 보면 '이게 왜 BFS문제지?' 라는 의문이 든다. S층에서 G층으로 가는데 U칸 위로가거나 D칸 아래로 가야하므로 1. 처음에 visited[S]를 방문 처리를 해주고 q에 S를 넣는다. 2. q에서 pop한 뒤 x + U에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을 누른 횟수를 1 증가시킨다. 3. 2번과 마찬가지로 x - D에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을..
www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 이제는 무난한(?) BFS문제이다. 단지 3차원배열을 사용해 조금 귀찮을 뿐이다. 1. Test Case마다 m(빌딩상태), time(이동시간), visited(방문여부) 배열을 초기화해주고 m을 입력받는다. 2. m을 전체돌면서 'S'가 있는 칸의 좌표를 sz, sx, sy에 저장하고, 'E'가 있는 칸의 좌표를 ez, ex, ey에 저장한다. 3. bfs를 돌리면서 다음 칸으로 갈때마다 시간을 1씩 더해주고 큐에..
www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net import sys from collections import deque input = sys.stdin.readline q = deque() M, N, H = map(int,input().split()) dx, dy, dz = [1,-1,0,0,0,0], [0,0,-1,1,0,0], [0,0,0,0,-1,1] m = [[list(map(int,input().split())) for _ ..
www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N * M칸의 map을 입력받고 BFS를 돌려준다. 1. (0,0)부터 시작하므로 q에 (0,0)을 넣고 BFS 시작 2. i가 0부터 3까지 돌면서 nx = x + dx[i], ny = y + dy[i]를 통해 현재 좌표의 상하좌우를 모두 '넓게' 탐색한다. 3. 만약 (nx,ny)를 방문한적이 없고 map[nx][ny]가 1이면 q에 넣고 dist[nx][ny]에 dist[x][y] + 1을 저장하고 (nx,ny)에 방문했다는 표시를 한다..
www.acmicpc.net/problem/1260 기초적인 그래프 탐색 문제이다. (그 동안 배우지 않고 어려워보여서 손을 안대고 있었는데, 막상 강의를 듣고 스터디도 하면서 문제를 많이 풀어보니 할 만한 것 같다.) 그래프 탐색방법에는 크게 2가지가 있다. 바로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이다. DFS(Depth First Search) - 깊이 우선 탐색이란, 쉽게 말해 한 정점을 정해 끝까지 파고들어가는 방법이다. - 모든 노드를 방문하고자 할 때 이 방법을 쓴다. - 자기 자신을 호출하는 재귀방식을 사용한다. - 시간 복잡도 = O(V + E) (V: 정점의 수, E: 간선의 수) 단점 - BFS에 비해 조금 느리다. - DFS는 해를 구하면 탐색이 종료되므로, 구한 해가..
모르는 사이에 조금씩 조금씩..
