coding tasty house

문제 https://www.acmicpc.net/problem/2146 알고리즘1. bfs그래프 탐색을 통해서 1로 되어 있는 땅을 2, 3, 4 .. 으로 각 구역을 숫자로 구분한다2. 다음 bfs 탐색을 통해서 시작 구역의 위치를 queue에 담아둔다 3. 탐색 과정에서 자신의 구역과 다른 구역을 만났을 때 최단거리를 반환한다 코드 import sysfrom collections import dequedef Input_Data(): input = sys.stdin.readline N = int(input()) graph = [] for _ in range(N+1): graph.append(list(map(int, input().split()))) return N..

문제 https://www.acmicpc.net/problem/5014코드import sysfrom collections import dequedef Bfs(): q = deque() q.append(S) visited[S] = 1 while q: x = q.popleft() # 위로 가는 경우 if (x+U0): if visited[x-D] == 0: #방문하지 않았으면 방문 visited[x-D] = visited[x] + 1 q.append(x - D) # 도달하지 못한 경우 if visited[G] == 0: return "use th..

문제https://www.acmicpc.net/problem/6593 코드import sysfrom collections import dequeinput = sys.stdin.readlined = ((1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1))def Bfs(start_l, start_x, start_y): q = deque() q.append((start_l, start_x, start_y)) visited[start_l][start_x][start_y] = 1 while q: v, x, y = q.popleft() if v == end_l and x == end_x and y == end_y: ..

https://www.acmicpc.net/problem/10026    import sysfrom collections import dequedef Input_Data(): readl = sys.stdin.readline N = int(input()) graph = [list(input()) for _ in range(N)] return N, graph d = ((1,0), (0,1), (-1, 0), (0,-1))def Bfs(i,j,color): q = deque() q.append((i,j)) visited[i][j] = 1 while q: x,y = q.popleft() for dx, dy in d: nx..

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 알고리즘 1. 주어진 사각형의 좌표를 조회해서 해당영역을 그래프에 1로 채워준다 (초기화 0으로) 2. 2차원 그래프를 조회해서 0으로 시작되는 구역이 나올때 section의 값을 올려준다 3. bfs순회시, 방문때 이미 간 곳은 2로 바꿔준다 코드 import sys from collections import deque def input_data(): readl = sy..

문제설명 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 알고리즘 1. 그래프 정보 입력 2. 고슴도치 위치, 홍수 지역 정보 저장 3. 홍수 정보를 통해 1분당 홍수 그래프에 반영 4. 고슴도치 이동 반복 코드 import sys from collections import deque def Input_Data(): R, C = map(int,readl().split()) map_forest = [[0] + list(readl()[:-1]) + [0] if 1

문제설명 https://school.programmers.co.kr/learn/courses/30/lessons/1844 코드 #include #include #include using namespace std; int visited[101][101]={}; int dx[4]= {-1,1,0,0}; int dy[4]= {0,0,-1,1}; int solution(vector maps) { int answer = 0; queue q; q.push({0,0}); visited[0][0] = 1; while(!q.empty()){ int x = q.front().first; int y = q.front().second; q.pop(); for(int i=0; i< 4; i++){ int nx = x + dx[..

문제설명 토마토가 상자안에 들어있다 가로M, 세로N, 높이 H로 상자가 주어진다 1은 토마토가 익어있다는 의미이고, -1은 빈 공간이다. 하루마다 익은 토마토를 기점으로 위,아래, 상,하,좌,우가 익는다 모든 토마토가 다 익는데 걸리는 최소한의 기간을 출력시킨다 단, 토마토가 원래 다 익어있는 경우에는 0을 출력하고, 토마토가 다 익지 못하는 경우는 -1을 출력시킨다 알고리즘 1. 입력 정보 받기 2. 그래프의 값이 1인(토마토가 익은경우) queue에 그 좌표값을 넣는다 3. bfs알고리즘을 사용하여 상,하,좌,우, 위, 아래를 모두 확인한다 4. 방문기록을 조회하여 0이 남아있는 경우 -1을 출력하고 그렇지 않은 경우엔 최대값을 출력시킨다 코드 #include #include #include usin..

문제설명 주어진 노드의 수, 도로 개수, 거리정보, 출발 도시의 정보를 입력 받은 뒤, 거리 정보가 일치하는 섬을 출력시키는 문제이다 이때 섬은 단방향으로만 연결 되어있으며 , 범위는 위의 사진과 같다 알고리즘 1. 주어진 정보를 입력 받는다 2. 간선의 정보를 단방향으로 벡터에 넣는다 3. bfs 알고리즘을 사용하되 , 각 노드에 도달하는데 걸리는 값을 방문 여부에 저장한다(이때 시작점으로 돌아가는 경우는 제외) 4. 각 노드에 도달하기 위해 필요한 값을 K와 일치하는지 비교하고, 일치하면 벡터에 넣는다 5. 벡터가 비어있는 경우 -1을 출력한다 코드 #include #include #include #include using namespace std; vector road; int N, M, K, X;..

문제설명 이 문제는 연결관계를 파악하여 해킹 가능한 컴퓨터가 많은 컴퓨터를 출력한다 만약 그 갯수가 동일하다면, 컴퓨터의 번호를 오름차순으로 출력한다 알고리즘 1. 컴퓨터의 수와 간선의 관계를 입력받는다 2. 간선의 관계는 단방향으로 저장한다(b가 해킹되면 a도 가능하다) 3. bfs 함수에서 각 컴퓨터가 해킹가능한 컴퓨터의 수를 센다 4. 컴퓨터의 수와 컴퓨터 번호를 저장한다 5. 정렬을 통해 해킹 할 수 있는 컴퓨터의 수가 가장 많은것, 그리고 인덱스는 오름차순으로 정렬한다 6. 첫 값은 무조건 가장 크기때문에 이와 같은 값인 컴퓨터의 인덱스를 모두 출력한다 코드 #include #include #include #include using namespace std; vector graph[10001];..