1. 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net S에 존재하는 고슴도치가 탈출지점 D로 이동해야하는데, 지도상에 물이 있고, 이 물도 1초에 1번씩 상하좌우로 퍼져나간다. 여기서 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다 가장 빠른 시간에 탈출할려면 얼마나 걸리는지 구하세요. 2. 나의 풀이 풀이는 전형적인 BFS로 시작점, 도착점을 찾고 물도 퍼져나가기 때문에 물이 어디에 있는지도 큐에 담아놔야겠다 r,c = map(int,stdin.r..
1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net N*M 행렬에서 (0,0)에서 출발하여 (n-1,m-1)로 이동하는 최단 거리를 구하는 문제지만, 벽으로 표현되는 1을 뚫고 지나가서 거리가 줄어든다면 단 1번만 허용할때, 최단거리를 구한다면..? 2. 풀이 bfs로 벽이 있더라도, 단 1번도 뚫지 않았다면 1번만 뚫고 1번 뚫었다면 그 뒤로는 벽을 지나가지 않도록 bfs 탐색하면 될것 같았는데 2차원 배열로 ..
1. 문제1 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 나이트가 최소 몇번 이동하면 주어진 칸으로 이동할 수 있는지 구하는 문제 어렵게 생각할 필요 전혀 없이, 문제에서 주어지는 1번에 이동할 수 있는 경우를 모두 델타배열에 저장하여, 그것을 순회하면 된다 2. 풀이 어렵게 생각할 필요 전혀 없고 일반적인 bfs 흐름으로 가다가 상하좌우 델타배열 [[0,1],[1,0],[0,-1],[-1,0]]을 나이트가 이동할 수 있는 칸으로 바꾼 델타배..
1. 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 0과 1로 이루어진 2차원 배열에서 1로만 이루어진 영역을 구분지어서 영역이 몇개인지, 혹은 각 영역이 이루는 땅의 개수?가 몇개인지 구하는 문제 모두 BFS/DFS로 해결할 수 있다 기본적으로 (0,0)부터 탐색을 시작해서 전체를 탐색하는게 BFS/DFS의 기본이기는 한데 이렇게 하면 문제가 상당히 어렵다 중간에 0을 만나면 어떻게 건너 뛰어서 다른 영역을 찾아야한다는게 그게 쉽지는 않..
1. 기본 스택 구현 방문배열 visited 초기화 첫 시작정점 v를 방문 처리 그 후 탐색 반복문 수행 v에 인접한 정점 w중에서 아직 방문하지 않은 w를 찾으면, 이미 방문한 v를 스택에 넣고 v를 w로 교체한 후에, w를 방문처리하고 바로 break 그 후 다시 w에 인접한 정점중에서 방문하지 않은 정점을 찾으면, w를 스택에 넣고 새로운 정점으로 교체한 뒤에 방문처리하고 반복 수행 더 이상 방문할 곳이 존재하지 않는다면 스택이 비어있는지 검사한다 스택이 비어있다면, 전체 탐색을 종료 스택이 비어있지 않다면, 하나씩 pop하여 다시 인접한 정점중에서 방문하지 않은 정점이 존재하는지 탐색 수행 visited = [0] * n def dfs(v,visited): visited[v] = 1 stack =..
1. 가장 기본형태 방문배열 visited 생성 빈 큐에 방문 시작할 정점 v를 넣고 v에 대한 방문처리 큐가 빌때까지 반복문 - 큐에서 정점 v를 빼고 v에 대해 할일을 수행하면서 v에 인접한 정점 w중에 방문하지 않은 w라면 다시 큐에 넣고 w에 대해 방문처리 def bfs(v,N): #시작정점 v, 마지막 정점 N #visited 생성 visited = [0] * (N+1) #큐를 생성함 q = [] q.append(v) #시작점이 들어간 큐 ### q=[v] visited[v] = 1 while q: #큐가 비어있지 않다면 탐색 v = q.pop(0) #시작점 뽑아내기 #방문한 v를 이용해 할일 print(v) #인접하고 미방문한 (in queue되지 않은) 정점 w가 있으면... for w in..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
