본문 바로가기

알고리즘/백준34

[백준] 2667번 단지번호붙이기 Java (DFS, BFS) 그래프 관련 문제들의 유형이 다 비슷비슷 한 것 같아보인다. 확실히 짚고 넘어가야 할 필요를 느꼈다. 물론 돌아서면 까먹어서 문제.. 문제링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 최대한 main 부분은 건드리지 않고 DFS, BFS 부분만 바꿔서 정리 하려고 노력했.. 2020. 2. 16.
[백준] 7569번 토마토 이전 문제와 같은데 입력만 한번 더 받은 문제였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113package baekjun; import java.util.LinkedList;import java.util.Queue;import java.util.Scanner; class Coor{ int x; int y; int z; Coor(int x,.. 2018. 8. 27.
[백준] 7576번 토마토 - 기억할 것1. 익은 토마토가 있는 곳 = 행렬의 값이 1인 지점을 시작점으로 해야한다. >> 처음에 행렬 값이 1인 x,y 좌표를 먼저 저장한다.2. 애초에 다 익은 경우 0을 출력, 다 익지 못하는 경우 -1을 출력3. 익은 토마트 = 안익은 토마토 + 14. 현재 있는 위치가 (x,y) 라면 그 다음 갈 수 있는 좌표는 인접해 있는 상,하,좌,우 칸입니다. 즉, 상 : (x-1,y) , 하 : (x+1,y), 좌 : (x,y-1), 우 : (x, y+1) 이므로 이를 4개의 순서쌍으로 생각해서 배열로 만들 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555.. 2018. 8. 21.
[백준] 1260 DFS와 BFS DFS와 BFS를 공부하고 좋은 예제를 찾아보다가 백준 알고리즘을 찾게되었다.DFS는 스택을 이용한 방식으로 현 경로상의 노드만을 기억하면 되기때문에 저장공간의 수요가 적다.목표노드가 깊은 곳에 있는 경우 빨리 구할 수 있다. BFS는 큐를 이용한 방식이다. 현 노드에서 인접한 노드를 모두 들리면서 탐색하는 방식이다. 문제. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.입력. 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 .. 2018. 8. 20.
백준 2747, 2748 피보나치 수 오늘 간단한 피보나치 수열 문제를 풀다가 의외의 복병에 만나서 헤매게 되었다.백준 2747문제 n번 째 = 45 까지백준 2748문제 n번 째 = 90 까지문제의 형태는 같은데 입력 받을 수 있는 수의 크기가 차이나는 문제였다. 2747번 문제를 아무 생각없이 배열과 반복문을 사용해서 제출했는데 "틀렸습니다"왜그런가 하고 재귀함수를 써서 했더니 "정답" 그리고 2748번 문제는 2747을 복붙했더니 역시나 "틀렸습니다"다시 원래 배열과 반복문을 사용했더니 "정답" 왜그럴까? 정답은 속도 차이에 있었다. 2747번 문제는 45번까지라 단순히 재귀함수를 사용해서 풀게끔 의도가 되어있었다. (값이 작음)하지만 2748번 문제는 n 이 90까지인데 재귀함수를 사용할 경우 호출이 누적되면서 실행시간이 매우 오래걸.. 2018. 8. 6.
백준 10866번 덱(Deque) 1. Deque(덱) 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐 어떻게 사용하느냐에 따라 큐와 스택이 모두 될 수 있음 2. Deque관련 메소드 1. 추가 add, addFirst, addLast, put, putFirst, putLast, offer, offerFirst, offerLast // Deque 마지막에 element삽입, first와 last자리삽입 push : Deque 앞 부분에 element 삽입 2. 삭제 poll : Deque의 제일 앞 element를 return받은 후 element 제거, 큐에서 element받아오기 pop : Deque의 제일 앞 element를 return받은 후 element 제거, 스택에서 element받기 * 큐의 경우 FIFO 이기 .. 2018. 7. 30.

티스토리툴바