-
[B14502][연구소][java]
2024.06.01
코드package com.example.algorithm.study.week14;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;// 벽 세울 세 곳 정하고 (DFS) 바이러스 퍼지고 나서(BFS) 최댓값 갱신 ?// 처음에는 오래걸리지 않나 싶고 시간초과라고 생각했다public class B14502_연구소 { static int n, m, max = Integer.MIN_VALUE; static int[][] arr, virus; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -..
-
-
[B11725][트리의 부모 찾기][java]
2023.10.08
https://www.acmicpc.net/problem/11725 풀이 (DFS) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.par..
-
[B7576][토마토][java]
2023.10.08
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) { } }
-
[B2667][단지번호붙이기][java]
2023.10.08
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Arrays; import java.util.Queue; import java.util.StringTokenizer; public class Mai..
-
[B2178][미로 탐색][java]
2023.10.08
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // 이동할 때마다 이동 횟수를 (전 칸 + 1) 해주는 것 // 그래야 같은 거리로 이동한 칸들을 같게..
-
[B1260][DFS와 BFS][java]
2023.10.08
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Mai..
-
[B2606][바이러스][java]
2023.10.08
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; // 차례대로 큐에 넣고 꺼내면서 인접해있는지 판단하는 흐름은 기억이 났는데 // 막상 짜려니까 오랜만에 BFS 풀어서 구조가 생각이 잘 안 났다. public class Main { public ..
-
[B7569][토마토][C++]
2021.08.17
#include #include #include using namespace std; int n, m, h; int map[102][102][102]; int dz[6] = { 0,0,0 ,0,-1,1 }; int dx[6] = { 0,0 ,1,-1,0,0 }; int dy[6] = { -1,1,0,0,0,0 }; int d[102][102][102]; int day = 0; int main() { ios::sync_with_stdio(NULL); cin.tie(0); cin >> m >> n >> h; queue Q; for (int i = 0; i > map[i][..
-
[B2667][단지 번호 붙이기][C++]
2021.07.20
#include #include #include #include #include using namespace std; int arr[30][30]; bool isVisit[30][30]; int dx[4] = { 0,0,1,-1 }; int dy[4] = { -1,1,0,0 }; int n, cnt = 0; vector ans; queue q; int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf_s("%1d", &arr[i][j]); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 1 && isVisit..
-
[B2178][미로 탐색][C++]
2021.07.16
#include #include #include using namespace std; string s[101]; int dis[101][101]; bool isVisit[101][101]; queue Q; int n, m; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; for (int i = 0; i > s[i]; dis[0][0] = 1; Q.push({ 0,0 }); isVisit[0][0] = true; while (!Q.empty()) { pair tmp = Q.front(); Q.pop..
-
[B1389][케빈 베이컨의 6단계 법칙][C++]
2021.07.12
#include #include #include using namespace std; int map[101][101]; bool chk[101]; int main() { int n, m; cin >> n >> m; int input1; int input2; for (int i = 0; i > input1 >> input2; map[input1][input2] = 1; map[input2][input1] = 1; } queue q; int sum = 0; int result = 999999; int people = 0; for (int i = 1; i
-
[B1260][DFS와 BFS][C++]
2021.06.23
#include #include using namespace std; int n, m, v; int map[1001][1001]; bool visit[1001]; queue Q; void DFS(int v) { visit[v] = true; cout x >> y; map[x][y] = 1; map[y][x] = 1; } for (int i = 1; i
-
[B11724][연결 요소의 개수][C++]
2021.06.15
#include #include using namespace std; const int MAX = 1001; queue Q; int map[MAX][MAX] = { 0, }; bool visit[MAX] = { 0, }; int n, m, cnt = 0; int s, f; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; for (int i = 0; i > s >> f; map[s][f] = 1; map[f][s] = 1; } for (int i = 1; i
-
[B1697][숨바꼭질][C++]
2021.06.11
#include #include using namespace std; // 걷기 : 1초 후에 x-1 or x+1 이동 // 순간이동 : 1초 후에 2*x 이동 const int Max = 100001; int n, k, fl, fs; bool isVisit[Max]; queue Q; int main(void) { cin >> n >> k; Q.push(make_pair(n, 0)); isVisit[n] = true; while (!Q.empty()) { fl = Q.front().first; fs = Q.front().second; Q.pop(); if (fl == k) break; if (fl + 1 < Max && !isVisit[fl + 1]) { // +1 Q.push(make_pair(fl +..
-
[B1697][숨바꼭질][python]
2021.06.11
import sys from collections import deque limit = 100001 def solve(arr, n, k): q = deque() q.append(n) while q: i = q.popleft() if i == k: return arr[i] for j in (i+1, i-1, 2*i): if (0
-
[B7576][토마토][C++]
2021.06.10
보관 후, 하루가 지나면 익은 토마토의 인접한 곳에 익지 않은 토마토들은 익게 됨 (인접한 곳 - 왼, 오, 앞, 뒤) 혼자 저절로 익는 경우는 없음 며칠이 지나면 다 익게 되는가? m,n - 상자 가로, 세로 1 - 익은 토마토 0 - 익지 않은 토마토 -1 - 토마토가 들어있지 않음 최소 날짜 출력 (모든 토마토 익어있음 = 0, 모두 익지 못함 = -1) #include #include using namespace std; int m, n, cnt; int map[1001][1001]; bool isVisit[1001][1001]; int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,-1,1 }; queue Q; int main(void) { ios::sync_with_s..
-
[B2606][바이러스][C++]
2021.06.09
## BFS (너비 우선 탐색) - Queue 이용 #include #include using namespace std; int virus[101][101]; int visit[101]; int c, n, cnt; int main(void) { cin >> c; cin >> n; for (int i = 0; i > s >> f; virus[s][f] = 1; virus[f][s] = 1; } visit[1] = 1; queue Q; Q.push(1); while (!Q.empty()) { int node = Q.front(); Q.pop(); for (int i = 1; i
-
[B1012][유기농 배추][C++]
2021.06.07
#include #include using namespace std; //가로길이 m = 열, 세로길이 n = 행 //BFS(Breadth-first search) : 너비우선탐색 - 인접한 노드 먼저(얕은 노드 -> 깊은 노드) //DFS(Depth-First Search) : 깊이우선탐색 - //큐 - FIFO 이용 //1. 타겟 발견 //2. 맵 벗어났나 //3. 이미 방문한 타겟인가 int t; int m, n, k; int map[50][50]; bool visit[50][50]; int result; queue Q; int dr[4] = { -1,1,0,0 }; int dc[4] = { 0,0,-1,1 }; int main() { cin >> t; while (t--) { cin >> m >>..
-
[B1012][유기농 배추][python]
2021.06.07
import sys t = int(sys.stdin.readline()) dr = [1, -1, 0, 0] dc = [0, 0, -1, 1] for i in range(t): m, n, k = map(int, sys.stdin.readline().split()) cabbage = [[0] * m for cb in range(n)] cnt = 0 for j in range(k): c, r = map(int, sys.stdin.readline().split()) cabbage[r][c] = 1 for q in range(n): for w in range(m): if cabbage[q][w] == 1: queue = [[q, w]] while queue: fr, fc = queue[0][0], queue[0]..
