본문 바로가기

dfs8

[Java/백준/DFS, DP] 1937번: 욕심쟁이 판다 문제 링크 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 골드 3 문제다. 읽자마자 실버 수준의 DFS로 풀었다가 슬픈 결과를 여러번 맞이했다. 아래부터 1) DFS만 사용했다가 시간초과 발생 2) DP 사용했는데 max값 잘못 계산 반례 : 2 2 2 2 2 3) 성공 시간초과 코드 DFS만 이용한 경우이다. boolean[][] visited를 매개변수로 가지고 이동하면서 선택한 블록에 대한 경로를 저장한다. dfs에서 cnt는 더 이상 갈 블.. 2021. 4. 23.
[Java/BFS] 1868. 파핑파핑 지뢰찾기 문제 링크 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 아이디어 1. map 배열의 전체를 돌면서 8방탐색을 한다. → 8방에 지뢰가 몇개 있는지 체크해서 mark 배열에 저장한다. 2. mark가 0이고(주변에 지뢰가 없고) && 클릭한 적 없고 (visited가 false) && 지뢰가 아닌 곳(map이 0)인 곳 CLICK 3. 2에서 아직 클릭 안한 곳 && 지뢰가 아닌 곳 CLICK 왜인지 시행착오가 좀 많았다.. 0인 곳을 누르면 주변의 0인 곳.. 2021. 4. 23.
[Java/백준/백트레킹] 1987번: 알파벳 문제 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백트래킹 너무 어렵다ㅠㅠ.... 일단 백트래킹이란 걸 처음에 알아보는 것부터 아직 어설프다... 앞으로 DFS를 사용해야 할 것 같다, 가지치기 할 수 있을 것 같다 하면 걍 백트래킹으로 해야지.. 시행착오가 좀 있었다. 처음엔 alphabet을 사용했는지 여부만 알아보는 코드이다. 기저조건은 그냥 썼던 알파벳일때 return max는 다 dfs를 돌고 나왔다 싶을 해줬다. 근데 이러면 안될 것 같.. 2021. 2. 18.
[Java/SWEA/백트래킹] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로 문제 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE&problemTitle=1247&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 조건을 보면 집 → N명의 고객 → 회사 경로로 간다. 처음에 최단경로 라는 키워드를 보고서 BFS를 이용해야 하나 싶긴 했었다. 이렇게 하면 N명.. 2021. 2. 18.
[Java/프로그래머스/DFS] 여행경로 문제 programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 코드 처음엔 인접하는 공항들을 전부 adjacent에 넣어야 하는데 어떻게 해야할까 끙끙댔다. 다행히 tickets는 양방향이 아닌 순서가 있는 것이라, dfs함수의 if문에서 조건을 걸러낼 수 있었다. import java.util.ArrayList; import java.util.Collections; public class Solution { boolean[] visited; //방문한지.. 2020. 11. 5.
[Java/백준/DFS] 1012번: 유기농 배추 문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 코드 단지번호 붙이기와 비슷하게 풀었다 아이고 속시원해 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; class Main{ static int[] dx = {0,0,-1,1}; s.. 2020. 9. 19.
[Java/백준/DFS와 BFS] 2667 - 단지번호붙이기 문제 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 코드 DFS가 재귀를 써도 되기 때문에 자주 사용하게 된다. 입력받은 2차원 배열은 village에 저장한다. dx, dy를 사용해서 상하좌우 좌표를 정해준다. 이중 for문을 돌면서 1인 좌표를 발견하면 dfs함수를 호출한다. 굳이 visited를 사용하지 않아도 dfs가 시작되면 village의 해당 좌표 값을 0으로 바꾸어 준다. (그럼 다음에 쓰루함) 해당 좌표에서 dx, dy로 상하좌우를 탐색하면.. 2020. 9. 17.
[자료구조/Java] Graph 검색 DFS, BFS 구현 https://www.youtube.com/watch?v=_hxFgg7TLZQ 따르고 싶은 유튜브 선생님이 생겼다.......... 1. BFS : 넓이 우선 탐색 1) Queue로 구현 가능 시작 노드 하나를 큐에 넣고 시작 → 큐에서 하나 꺼내고 → 해당 노드의 자식 노드들을 하나씩 큐에 넣음 → 처음에 넣은 노드를 출력 → (큐가 빌 때까지 반복) 2. DFS : 깊이 우선 탐색 1) Stack으로 구현 가능 스택에 노드를 하나 넣고 시작 → 스택에서 노드를 꺼내고 → 자식 노드들을 넣고 → 꺼낸 노드를 출력 → (스택이 빌 때까지 반복) 2) 재귀 호출로 구현 가능 노드에 방문하면 우선 출력 → 자식들을 재귀로 호출 내용 정리 import java.util.LinkedList; import jav.. 2020. 8. 14.

티스토리툴바