알고리즘/DFS, BFS24

• 

  [백준] 1600번: 말이 되고픈 원숭이 - java 나의 풀이 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; public class Main { static StringBuilder sb; static BufferedReader br; static BufferedWriter bw; static StringTokenizer st; static int k, w, h; st.. 알고리즘/DFS, BFS 2023. 2. 24.

• 

  [백준] 3109번: 빵집 - java 나의 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int r, c; static char arr[][]; static int pipe; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer .. 알고리즘/DFS, BFS 2023. 2. 21.

• [백준] 6987번: 월드컵 - java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { /** * 기자가 보내온 각 나라의 승,무,패 결과 scores[i][j] -> i는 0~5까지이며 각각 "A~F" 를 의미한다. * -> j는 0,1,2로 각각 "승, 무, 패" 를 의미한다. */ static int[][] scores = new int[6][3]; static int isPossible; // i번째 경기에 출전하는 두 나라를 각각 aTeam, bTeam 에 저장한다. static int[] aTeam = { 0, 0, 0,.. 알고리즘/DFS, BFS 2023. 2. 21.

• 

  [백준] 14752번: 개미굴 - java import java.io.*; import java.util.*; public class Main { static class Node { Map child; public Node() { child = new HashMap(); } } static StringBuilder sb; static int n; static Node root; static Node cur; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; sb = new StringBuilder(); n = Integer... 알고리즘/DFS, BFS 2023. 2. 19.

• [백준] 1941번: 소문난 칠공주 - java 나의 코드 import java.io.*; import java.util.*; public class Main { static char[][] arr; static int[] selected; static int[] dx = {1, 0, -1, 0}; static int[] dy = {0, 1, 0, -1}; static int answer = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); arr = new char[5][5]; for (int i = 0; i < 5; i++) { String s = br.r.. 알고리즘/DFS, BFS 2023. 2. 19.

• [백준] 15683번: 감시 - java 나의풀이 import java.io.*; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static class Camera { int num; int x; int y; public Camera(int num, int x, int y) { this.num = num; this.x = x; this.y = y; } } static int n, m; static ArrayList cameras = new ArrayList(); static int min_spot = Integer.MAX_VALUE; static int[] dx = {0, 1, 0, -1}; static int[] dy = {1, 0, -1, 0.. 알고리즘/DFS, BFS 2023. 2. 19.

• [swea] 2806번: N-Queen - 파이썬(python) 백트래킹에 대한 문제를 거의 풀어보지 않아서, N-Queen 문제도 처음 접해보았다. BFS 와 대체로 비슷하지만, 더 이상 탐색할 필요가 없는걸 쳐내는 행위를 백트래킹 이라고 한다. 따라서, 한 행씩 퀸을 놓아보는데, 지금까지 같은열 or 대각선에 퀸이 있지 않다면 계속해서 BFS 를 진행하는 것이다. 이때, 한 행씩 퀸을 순서대로 놓기 때문에, 같은 행에 여러 퀸이 놓이는 경우는 고려하지 않아도 된다. row 리스트의 경우, 각 인덱스가 행번호를 의미하고, 각 인덱스값은 열번호를 의미한다. 즉, row의 i번째 행에 있는 값이 j라면, 퀸이 (i,j) 에 위치함을 뜻한다. 또한, visited 리스트를 두어 i번째 열에 퀸이 위치하는지를 확인할 수 있다. 이로 인해, visited[col] 에 이미 .. 알고리즘/DFS, BFS 2022. 11. 13.

• [swea] 5215번: 햄버거 다이어트 - 파이썬(python) 재료리스트, 칼로리리스트의 0~n-1 까지의 인덱스에 재료점수와 재료의 칼로리를 저장해둔다. 그런 다음 i번째 재료를 추가할지, 추가하지 않을지의 여부에 따라 DFS 를 진행해간다. i가 n 이라면, 1~n까지의 재료에 대해 모든 선택을 완료한 것이므로, DFS 를 종료한다. * 지금까지 구한 점수 + 현재 인덱스부터 끝 인덱스까지 점수를 모두 더한 값이 현재 max_score 이하라면, 굳이 검사를 하지 않아도 최댓값이 갱신되지 않으므로 바로 return 할 수 있다. 이는 시간을 줄일 수 있는 아주 좋은 방법이다. 나의 풀이 def dfs(i, total, calorie): global max_score if i == n: max_score = max(max_score, total) return # .. 알고리즘/DFS, BFS 2022. 11. 7.

• 

  [백준] 19236번: 청소년 상어 - 파이썬(python) 나의 풀이 from collections import deque import heapq import copy def move_fish(shark, fish) : for i in range(1,17) : # 1번~16번물고기까지 차례로 이동 x,y = fish[i][0],fish[i][1] if x==-1 or y==-1 : # 없어진 물고기 continue rotate = shark[x][y][1] # i번 물고기의 방향 for _ in range(8) : nx = x + dx[rotate%8] ny = y + dy[rotate%8] # 해당 방향의 다음 칸이 범위안이고, 빈칸이거나 물고기가 존재한다면 if 0 알고리즘/DFS, BFS 2022. 10. 24.

• 

  [백준] 16236번: 아기 상어 - 파이썬(python) 나의 풀이 from collections import deque n= int(input()) arr = [] now_x , now_y = -1, -1 # 아기 상어의 위치 length = 2 # 아기 상어의 크기 cnt = 0 # 아기 상어가 먹은 물고기 개수 time = 0 # 아기 상어가 물고기를 잡아먹는데 걸린 시간 m = 0 # 물고기 개수 for _ in range(n) : arr.append(list(map(int, input().split()))) for i in range(n) : for j in range(n) : if arr[i][j] == 9 : now_x = i now_y = j arr[i][j] = 0 elif arr[i][j] > 0 : m += 1 dx = [1,0,-1,0] .. 알고리즘/DFS, BFS 2022. 10. 24.

• 

  [프로그래머스] 블록 이동하기 - 파이썬(python) 문제 설명 로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다. 로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이.. 알고리즘/DFS, BFS 2022. 10. 9.

• [백준] 16234번: 인구 이동 - 파이썬(python) 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은.. 알고리즘/DFS, BFS 2022. 10. 8.