L.O.K

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ◎ 문제풀이 토마토가 익는 비용이 하루로 고정되어 있고 상하좌우로 이동가능하고 최소일수 즉, 최단거리를 구하는 문제이니 BFS 알고리즘이 떠올랐다. 그래서 BFS 알고리즘으로 풀었는데 시간초과가 발생했다. 돌이켜 생각해보니 나는 BFS를 가장한 DFS 풀이를 한거였다. 1 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 1 익어있는 토마토는 2..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ◎ 문제풀이 가중치 없는 그래프에서 최단거리를 구하는 문제는 BFS로 푼다. DFS는 깊이우선탐색으로 최악의 경우를 먼저 탐색할 가능성이 있어서 처리시간이 오래 걸린다. 넓이 우선 탐색으로 해야 최악의 경우를 사전에 방지할 수 있다. ◎ 코드 Python #BOJ2178 미로탐색 (bfs) import sys from collections import deque input = sys.stdin.readline n,m = map(..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ◎ 문제풀이 DFS, BFS 문제이다. DFS는 STACK, BFS는 QUEUE를 사용하면 된다. 재귀호출은 함수가 STACK 영역에 쌓이므로 재귀호출로 구현한다. 주의점 1) BFS에서 노드 방문이력은 큐에 들어가기 직전에 변경해야한다. 2) 양방향 관계임을 주의하자. 3) 인접노드 탐색시 오름차순 순으로 탐색해야 하므로 정렬이 필요하다. ◎ 코드 from ..

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net ◎ 문제풀이 그래프를 탐색하여 A ⇢ B ⇢ C ⇢ D ⇢ E 경우가 있는지 탐색해야 한다. 그래프의 탐색은 DFS와 BFS가 있다. 참조의 참조를 하는 문제이므로 DFS가 적절하다. DFS는 STACK으로 구현된다. STACK은 '기억' 기능이 있어서 함수가 호출되면 STACK 영역에 차례대로 쌓여 호출된 순서가 기억된다. 그러므로 DFS는 STACK을 직접 구현하지 않아도 재귀호출를 사용하면 된다. 위 문제를 풀면서 놓친 부분은 3가지가 있다. 1) 방문이력테이블이 필요하다는 생각 X 깊이탐색은 count가 4일때까지 이루어진다. 여기에는 재방문이 포함될 수 있다...

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ◎ 문제풀이 N에서 K를 구하는 문제이다. 연산은 3가지이다. +1, -1, x2 연산 한번에 1초가 소요되고 몇초가 걸리는지를 구하는 문제이므로, 연산횟수를 구하는 문제이다. 시작점과 목표점이 주어지고 최소연산횟수를 구하는 문제이다. 1) DP가 아니라 BFS 문제 나는 DP가 먼저 연상되었다. 그러나 DP보다는 BFS가 더 적합한 알고리즘이다. 그 이유는 '시작위치'에 있다. DP는 더이상 쪼갤 수 없는 시작위치에서 목표지점까지 구..

◎ 문제 N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. - 입력조건 첫째 줄에 두 정수 N, M(4 =m or y < 0 : return False else : return True q=deque() # 큐생성 q.append((0,0)) # 시작점 while q : pointX,pointY = q.popleft() # ..

음료수 얼려 먹기 문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다 입력 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 = maxY : return False else : return True # DFS 알고리즘 구현 함수 def dfs(x, y) : visited[x][y] = True # 방문처리 if not validateIndex(x,y) : r..