본문 바로가기

BFS68

[자바] 백준 14503 - 로봇 청소기 (java) 목차 문제 : boj14503 필요 알고리즘 구현, 시뮬레이션, 탐색 (bfs, dfs 등) 그냥 문제에 제시된 대로 구현하는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 딱히 풀이라 할 부분은 없을 것 같다. 문제에 제시된대로 구현하면 된다. 따라서 내 코드를 기준으로 어떤식으로 구현했는지만 얘기해보겠다. 우선 '방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 .. 2024. 3. 19.
[자바] 백준 1953 - 팀배분 (java) 목차 문제 : boj1953 필요 알고리즘 이분 그래프 (bipartite graph), 그래프 탐색 (BFS, DFS 등) 이분 그래프에 대한 개념이 있다면 좀 더 쉽게 풀 수 있는 그래프 탐색 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 2년전에 못 푼 기록이 있어 풀어봤다. 별 어려움 없이 바로 푼걸 보면 발전은 있었나보다. 2년전엔 HashSet을 사용해 넣을 때 마다 겹치는게 있는지 검색해본 것 같다. .. 2024. 2. 26.
[자바] 프로그래머스 - 석유 시추 ([PCCP 기출문제] 2번) (Lv2, Java) 목차 문제 : Programmers - [PCCP 기출문제] 2번 / 석유 시추 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 탐색 (BFS, DFS 등) 약간의 아이디어만 있다면 탐색 알고리즘으로 풀 수 있다. 풀이 우리가 알아야 하는건, 각 열 번호에서 접근 가능한 석유들의 합이다. cnt[X] 라는 배열을 정의해보자. 이건 X 인덱스 열에서 접근 가능한 석유들의 총 합을 뜻한다. 최종적으로 cnt[0] 부터 cnt[m-1] 까지의 값 중 가장 큰 값을 출력하면 될 것이다. 예를들어 아래와 같이 표현될 것이다. 최종적으로 cnt 배열에서 가장 큰 값이 9 이므로 9가 답이다. --- 그럼 이제 cnt[] 에 값을.. 2024. 1. 22.
[세미나] hashset, hashmap, BFS (기초 자료구조 및 알고리즘 5회차) 세미나 진행한 pdf 입니다. hashmap, hashset, BFS (너비 우선 탐색) 에 대해 다룹니다. 이후에 영상이나 음성이 필요하다고 생각되는 회차가 있으면 그것도 공유할 예정입니다. ppt의 우측 상단 '새 탭에서 보기' 를 누르시면 크게보거나 pdf를 다운받아 보실 수 있습니다. 2024. 1. 22.
[자바] 백준 13565 - 침투 (java) 목차 문제 : boj13565 필요 알고리즘 그래프 탐색 (bfs, dfs) 약간의 아이디어만 생각나면 dfs나 bfs 같은 그래프 탐색으로만 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 주어진 격자에서 맨윗줄 중 흰색(0)칸을 찾아 거기서부터 BFS를 계속 진행한다면 좀 귀찮다. 약간의 아이디어를 더한다면 BFS 한방에 해결할 수 있다. 아이디어는 생각보다 간단한데, 주어진 격자(이미지 좌측)의 맨위와 맨 .. 2023. 12. 15.
[자바] 백준 1375 - 나이 (java) 목차 문제 : boj1375 필요 알고리즘 그래프 탐색(bfs, dfs), 값/좌표 압축 값/좌표 압축이야 그냥 String을 쓰기 편하게 int로 바꾼 것 뿐이고, 풀이는 그냥 bfs를 썼다. 의외로 별다른 것 없이 bfs나 dfs로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 입력이 String으로 들어오는데 이 부분부터 처리해보자. 그냥 새로운 문자열이 들어오면 그걸 새로운 int로 바꿔주면 된다... 2023. 12. 14.
[자바] 백준 26598 - 색종이와 공예 (java) 목차 문제 : boj26598 필요 알고리즘 애드 혹(ad hoc), 그래프 탐색(dfs, bfs) 이 문제만의 규칙을 찾아 해결하는 애드혹 문제이다. 구현을 위해 그래프 탐색을 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 내 경우 이하의 로직으로 진행했다. 1. 맵의 좌측상단부터 우측 하단으로 진행하면서, 이미 찾은 직사각형임을 찾은 곳은 체크를 해둔다 (다시 직사각형의 여부를 확인하지 않아도 되도록). 2. .. 2023. 11. 28.
[자바] 백준 30536 - 시루의 산책 (java) 목차 문제 : boj30536 필요 알고리즘 그래프 이론, bfs (너비 우선 탐색) 문제에서 제시된 데이터를 그래프로 생각하고, 적절한 방식으로 탐색해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선.. 내 경우 맞왜틀을 많이 외친 문제였다 ㅠ. 그 이유는 아래와 같다. 1. 난 각 기둥의 상태가 'A. 다른 강아지 마킹 있음', 'B. 마킹은 없으나 다른 강아지 냄새가 영향을 끼침', 'C. .. 2023. 11. 28.
[자바] 백준 12886 - 돌 그룹 (java) 목차 문제 : boj12886 필요 알고리즘 그래프 탐색 의외로 탐색 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아이디어 문제이다. 예를들어 10개의 정수 중 8개 정수의 합이 100인 정수 8개가 존재하는지 알아내야 한다고 해보자. 직관적으로 우린 그냥 나머지 2개의 합이 '전체의합-100'인 2개가 존재하는지 찾게 될 것이다. 이 문제도 나머지의 관점에서 생각해보자. S=A+B+C라고 해보자. 이 때 A,B.. 2023. 11. 27.
[자바] 백준 23040 - 누텔라 트리 (Easy) (java) 목차 문제 : boj23040 필요 알고리즘 분리 집합 (union-find), 그래프 탐색 (bfs, dfs 등), 트리 (tree) 그래프 탐색과 분리 집합에 대한 개념이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 만약 서로 붙어 있는 빨간 정점 그룹들의 갯수를 알고 있다고 해보자. 그럼 간단하게 모든 검정 정점들에서 간선 1개로 갈 수 있는 모든 정점 중 빨간 정점 그룹의 수를 모두 세주면 끝나는 .. 2023. 11. 22.