그래프탐색 [백준] 1325번 효율적인 해킹 - Java, 자바 난이도 실버 1 문제 풀이 문제 접근 이 문제는 DFS와 BFS로 풀 수 있는 그래프 탐색 문제로, 나는 BFS로 풀었다. 처음에 인접행렬을 활용해 문제를 풀었는데 메모리 초과가 나왔다. N은 10,000보다 작거나 같으므로 시간복잡도를 어림 잡아 계산했을 때 O(N*N = 10억정도)가 나와 이것을 줄여주려고 인접리스트(V+E)로 바꿔 풀었다. 기본적인 BFS 문제와 동일하게 풀면 된다. ... 백준그래프탐색그래프탐색 [백준] 17836번 공주님을 구해라! - Java, 자바 난이도 골드 5 문제 풀이 최단시간을 출력해야하므로 BFS를 사용했다. X좌표, Y좌표, 현재 탐색 깊이, 그람의 유무 해당 정보들을 클래스로 만들었다. 탐색 하는 중에, 그람의 유무에 따라 작업을 나눠 주었다. 1) 그람이 있는 경우 맵의 값과 상관없이 다음 노드에 방문한 적이 없다면 이동한다. 2) 그람이 없는 경우 다음 노드 방문한 적 없으면 보드의 값이 9일 때만 지나간다. 보드값이 ... 백준그래프탐색그래프탐색 [백준] 14940번 쉬운 최단거리 난이도 골드 5 문제 풀이 BFS로 문제를 해결했다. 여기서 주의할 점은 "원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다." 이 부분이다. 위 조건을 따져주기 위해서 2차원 방문배열로 조건을 줘서 해결했다. 방문했거나 map의 값이 0인 경우 그대로 map[i][j]를 출력 아니라면 -1을 출력 코드... 백준그래프탐색그래프탐색 [BOJ] 14466번: 소가 길을 건너간 이유 6 (JAVA) 문제 해석 1. 일반 목초지 사이는 상하좌우 모두 움직일 수 있다. 2. 중간에 다리가 있다면, 다리를 꼭 건너야 한다. 즉, 소(2,2)는 소(2,3)까지 다리를 건너야할 수도 있지만, 그 길을 회피해 회색 화살표 길로 갈 수 있다. 소(3,3)은 다른 목초지에 가려면 무조건 다리를 건너야 하므로, 모든 소와 유효한 쌍이 된다. 풀이 1. 소가 있는 곳을 중심으로 BFS 탐색을 하여, 영역... 알고리즘그래프탐색그래프탐색 [BOJ] 11967번: 불켜기 (JAVA) 탐색을 언제, 어디에서 하는지가 굉장히 중요한 문제! 우선, 더 이상 상태 변경이 없을 때까지 탐색을 반복한다. 탐색 코드 cangoTmp: 탐색하기 전의 상태를 저장해 놓는다. 탐색한 곳에서 스위치를 켤 수 있는 곳의 cango값을 true로 변경한다. BFS 탐색을 돌고, 탐색한 곳에서 map의 List를 돌며 계속해서 스위치를 켠다 탐색 전과 다른 상태라면, 새로 갈 수 있는 곳이 생겼... 알고리즘그래프탐색그래프탐색 [BOJ] 2606 - 바이러스 입력 전체 컴퓨터의 갯수 네트워크상의 연결된 컴퓨터 쌍의 수 연결된 컴퓨터 쌍 출력 1번 컴퓨터가 바이러스 걸렸을 때 바이러스가 전염될 컴퓨터 갯수 전에 푼거랑 너무 같은 문제네,,? 전체중에 1번 컴퓨터랑 연결되어 있는 컴퓨터 갯수 세는 문제 = 연결된 링크 갯수 세는 문제 DFS (깊이 우선 탐색) 이용... python알고리즘boj그래프탐색boj [BOJ] 3109번: 빵집(Java) 알고리즘: 백트래킹, DFS 0행에서는 아무곳에서나 출발 할 수 있으므로 R길이만큼 돌며 깊이우선탐색 알고리즘을 실행한다. 탐색의 기저조건은 현재 Column이 마지막 Column일때. 그 외에는 삼방탐색을 하여 갈 곳을 정한다. 이 때, 지나온 곳은 'O'로 표시하여 다시 지나갈 수 없게 한다. 하나의 파이프라인이 만들어졌을 때(기저조건) 해당 칸에서 다시 탐색이 이루어지지 않도록 Flag... 그래프탐색그래프탐색 [BOJ] 10026번 적록색약(Java) 같은 색이 상하좌우 한곳이라도 인접해있으면 같은 area로 되므로, 깊이우선탐색을 통해 같은 구역을 확인한다. 문제에서 '같은 색상이 상하좌우로 인접해 있는 경우'라고 되어 있어서 상하좌우에 모두 인접해있어야 한다고 생각했었다...┗|｀O′|┛ 일반인이 보는 구역을 확인하기 위해 입력받은 배열 그대로 DFS를 돌린다. DFS를 돌리면서, 'G'색을 만나면 해당 인덱스에 대한 연산이 모두 끝난... 그래프탐색그래프탐색 [BOJ] 2667번 단지번호붙이기 (Java) 사방탐색 중 깊이우선탐색(DFS)를 사용하여 해결 기본 DFS코드에 단지 내 집의 수를 저장 할 cnt배열을 추가하였다. 따로 배열을 만들어 준 이유는 마지막에 sort를 해야하기 때문. 코드 더보기... 그래프탐색그래프탐색 [BOJ] 2606번 바이러스 (Java) 그래프 탐색(DFS)를 통해 인접 정점의 개수를 구하는 문제. 인접행렬을 boolean형으로 선언해 탐색하는 인덱스의 값이 true이고 visited배열이 false라면 탐색하며, 결과값 cnt 증가. 코드... 알고리즘그래프탐색그래프탐색 [BOJ] 5427번 불 (Java) 전형적인 BFS 시뮬레이션 문제! 모든 로직의 순서와 불이 번지는 과정만 꼼꼼히 작성해주면 된다. BFS 로직 순서 1. Depth가 늘어날 때 마다 불 확산 2. 가려는 길에 불이 있으면 Continue 3. 종료 조건 확인 4. 상근이 이동 가능 경로 탐색 불이 번지는 과정 1. 불이 새로 번진 곳을 저장할 리스트 선언 2. 현재 불 리스트를 돌며 새로 번진 리스트에 추가 3. 현재 불 ... 알고리즘그래프탐색그래프탐색 [BOJ] 3184번 양 (Java) 1. 양 또는 늑대가 있는 영역을 검사 (BFS) 2. 그래프를 돌며 양과 늑대의 위치 저장 3. 탐색 후, 양과 늑대 리스트 크기 비교 후 map에 반영... 알고리즘그래프탐색그래프탐색 [백준] 13549번 숨바꼭질 3 - Java, 자바 난이도 실버 5 문제 풀이 그래프 탐색, BFS로 해결 1697번 숨바꼭질에서 약간의 변형이 있는데 순간이동을 0초 후에 *2만큼 한다는 것이다. 순간이동할 때는 시간이 흐르지 않으므로 1초후에 발생하는 로직과 분리해서 처리한다. -1, +1 하는 위치를 구하기 전에 2인 위치를 먼저 계산했다. 여기서 포인트는 2인 위치만을 계산한게 아니라 최대 위치인 100,000까지 전부 계산해둬야한다.... 백준그래프탐색그래프탐색 [백준] 1697번 숨바꼭질 - Java, 자바 난이도 실버 1 문제 풀이 그래프탐색 문제 가장 빠른 시간을 구해야하는 문제여서 BFS로 접근했다. 이 문제에서 헤맸던 점은 걸린 시간을 count로 코드로 짜다보니 결과가 너무 크게 나왔다. 시간을 어떻게 처리할지 고민을 하다가 1차원 배열에 저장하는 식으로 문제를 해결했다. BFS문제에서 배열에 값을 저장하며 문제를 해결하는 경우가 많은데(ex. 토마토) 이 문제도 그렇게 접근하여 풀면 ... 백준그래프탐색그래프탐색 <BOJ>10026번: 적록색약 BFS 코드 틀을 알고 있으면 쉽게 풀 수 있는 전형적인 BFS 문제이다. 현재 좌표와 다음 좌표의 색상이 같으면 이동하는 방식으로 탐색한다. 2중 for문으로 방문하지 않은 좌표인지 파악해서 해당 좌표에서 BFS를 호출한다. 이 때 카운팅을 한다. → 각 색상별로 영역이 몇 개인지 파악함 적록색약인 경우를 위해 G영역을 R영역으로 바꾸고, visited를 초기화 한 뒤 다시 탐색한다.... pythonBFSboj너비우선탐색그래프탐색그래프백준BFS 7562번 나이트의 이동 파이썬 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l ×... 백준BFS알고리즘그래프탐색BFS <BOJ>7562번: 나이트의 이동 BFS의 틀을 알면 바로 풀 수 있는 문제 중의 하나다. dx[], dy[]로 나이트의 이동 방향을 미리 초기화 한다. Flood Fill을 통해 목표 지점까지의 거리를 계산하면 된다.... Java그래프그래프탐색BFS너비우선탐색boj백준BFS
[백준] 1325번 효율적인 해킹 - Java, 자바 난이도 실버 1 문제 풀이 문제 접근 이 문제는 DFS와 BFS로 풀 수 있는 그래프 탐색 문제로, 나는 BFS로 풀었다. 처음에 인접행렬을 활용해 문제를 풀었는데 메모리 초과가 나왔다. N은 10,000보다 작거나 같으므로 시간복잡도를 어림 잡아 계산했을 때 O(N*N = 10억정도)가 나와 이것을 줄여주려고 인접리스트(V+E)로 바꿔 풀었다. 기본적인 BFS 문제와 동일하게 풀면 된다. ... 백준그래프탐색그래프탐색 [백준] 17836번 공주님을 구해라! - Java, 자바 난이도 골드 5 문제 풀이 최단시간을 출력해야하므로 BFS를 사용했다. X좌표, Y좌표, 현재 탐색 깊이, 그람의 유무 해당 정보들을 클래스로 만들었다. 탐색 하는 중에, 그람의 유무에 따라 작업을 나눠 주었다. 1) 그람이 있는 경우 맵의 값과 상관없이 다음 노드에 방문한 적이 없다면 이동한다. 2) 그람이 없는 경우 다음 노드 방문한 적 없으면 보드의 값이 9일 때만 지나간다. 보드값이 ... 백준그래프탐색그래프탐색 [백준] 14940번 쉬운 최단거리 난이도 골드 5 문제 풀이 BFS로 문제를 해결했다. 여기서 주의할 점은 "원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다." 이 부분이다. 위 조건을 따져주기 위해서 2차원 방문배열로 조건을 줘서 해결했다. 방문했거나 map의 값이 0인 경우 그대로 map[i][j]를 출력 아니라면 -1을 출력 코드... 백준그래프탐색그래프탐색 [BOJ] 14466번: 소가 길을 건너간 이유 6 (JAVA) 문제 해석 1. 일반 목초지 사이는 상하좌우 모두 움직일 수 있다. 2. 중간에 다리가 있다면, 다리를 꼭 건너야 한다. 즉, 소(2,2)는 소(2,3)까지 다리를 건너야할 수도 있지만, 그 길을 회피해 회색 화살표 길로 갈 수 있다. 소(3,3)은 다른 목초지에 가려면 무조건 다리를 건너야 하므로, 모든 소와 유효한 쌍이 된다. 풀이 1. 소가 있는 곳을 중심으로 BFS 탐색을 하여, 영역... 알고리즘그래프탐색그래프탐색 [BOJ] 11967번: 불켜기 (JAVA) 탐색을 언제, 어디에서 하는지가 굉장히 중요한 문제! 우선, 더 이상 상태 변경이 없을 때까지 탐색을 반복한다. 탐색 코드 cangoTmp: 탐색하기 전의 상태를 저장해 놓는다. 탐색한 곳에서 스위치를 켤 수 있는 곳의 cango값을 true로 변경한다. BFS 탐색을 돌고, 탐색한 곳에서 map의 List를 돌며 계속해서 스위치를 켠다 탐색 전과 다른 상태라면, 새로 갈 수 있는 곳이 생겼... 알고리즘그래프탐색그래프탐색 [BOJ] 2606 - 바이러스 입력 전체 컴퓨터의 갯수 네트워크상의 연결된 컴퓨터 쌍의 수 연결된 컴퓨터 쌍 출력 1번 컴퓨터가 바이러스 걸렸을 때 바이러스가 전염될 컴퓨터 갯수 전에 푼거랑 너무 같은 문제네,,? 전체중에 1번 컴퓨터랑 연결되어 있는 컴퓨터 갯수 세는 문제 = 연결된 링크 갯수 세는 문제 DFS (깊이 우선 탐색) 이용... python알고리즘boj그래프탐색boj [BOJ] 3109번: 빵집(Java) 알고리즘: 백트래킹, DFS 0행에서는 아무곳에서나 출발 할 수 있으므로 R길이만큼 돌며 깊이우선탐색 알고리즘을 실행한다. 탐색의 기저조건은 현재 Column이 마지막 Column일때. 그 외에는 삼방탐색을 하여 갈 곳을 정한다. 이 때, 지나온 곳은 'O'로 표시하여 다시 지나갈 수 없게 한다. 하나의 파이프라인이 만들어졌을 때(기저조건) 해당 칸에서 다시 탐색이 이루어지지 않도록 Flag... 그래프탐색그래프탐색 [BOJ] 10026번 적록색약(Java) 같은 색이 상하좌우 한곳이라도 인접해있으면 같은 area로 되므로, 깊이우선탐색을 통해 같은 구역을 확인한다. 문제에서 '같은 색상이 상하좌우로 인접해 있는 경우'라고 되어 있어서 상하좌우에 모두 인접해있어야 한다고 생각했었다...┗|｀O′|┛ 일반인이 보는 구역을 확인하기 위해 입력받은 배열 그대로 DFS를 돌린다. DFS를 돌리면서, 'G'색을 만나면 해당 인덱스에 대한 연산이 모두 끝난... 그래프탐색그래프탐색 [BOJ] 2667번 단지번호붙이기 (Java) 사방탐색 중 깊이우선탐색(DFS)를 사용하여 해결 기본 DFS코드에 단지 내 집의 수를 저장 할 cnt배열을 추가하였다. 따로 배열을 만들어 준 이유는 마지막에 sort를 해야하기 때문. 코드 더보기... 그래프탐색그래프탐색 [BOJ] 2606번 바이러스 (Java) 그래프 탐색(DFS)를 통해 인접 정점의 개수를 구하는 문제. 인접행렬을 boolean형으로 선언해 탐색하는 인덱스의 값이 true이고 visited배열이 false라면 탐색하며, 결과값 cnt 증가. 코드... 알고리즘그래프탐색그래프탐색 [BOJ] 5427번 불 (Java) 전형적인 BFS 시뮬레이션 문제! 모든 로직의 순서와 불이 번지는 과정만 꼼꼼히 작성해주면 된다. BFS 로직 순서 1. Depth가 늘어날 때 마다 불 확산 2. 가려는 길에 불이 있으면 Continue 3. 종료 조건 확인 4. 상근이 이동 가능 경로 탐색 불이 번지는 과정 1. 불이 새로 번진 곳을 저장할 리스트 선언 2. 현재 불 리스트를 돌며 새로 번진 리스트에 추가 3. 현재 불 ... 알고리즘그래프탐색그래프탐색 [BOJ] 3184번 양 (Java) 1. 양 또는 늑대가 있는 영역을 검사 (BFS) 2. 그래프를 돌며 양과 늑대의 위치 저장 3. 탐색 후, 양과 늑대 리스트 크기 비교 후 map에 반영... 알고리즘그래프탐색그래프탐색 [백준] 13549번 숨바꼭질 3 - Java, 자바 난이도 실버 5 문제 풀이 그래프 탐색, BFS로 해결 1697번 숨바꼭질에서 약간의 변형이 있는데 순간이동을 0초 후에 *2만큼 한다는 것이다. 순간이동할 때는 시간이 흐르지 않으므로 1초후에 발생하는 로직과 분리해서 처리한다. -1, +1 하는 위치를 구하기 전에 2인 위치를 먼저 계산했다. 여기서 포인트는 2인 위치만을 계산한게 아니라 최대 위치인 100,000까지 전부 계산해둬야한다.... 백준그래프탐색그래프탐색 [백준] 1697번 숨바꼭질 - Java, 자바 난이도 실버 1 문제 풀이 그래프탐색 문제 가장 빠른 시간을 구해야하는 문제여서 BFS로 접근했다. 이 문제에서 헤맸던 점은 걸린 시간을 count로 코드로 짜다보니 결과가 너무 크게 나왔다. 시간을 어떻게 처리할지 고민을 하다가 1차원 배열에 저장하는 식으로 문제를 해결했다. BFS문제에서 배열에 값을 저장하며 문제를 해결하는 경우가 많은데(ex. 토마토) 이 문제도 그렇게 접근하여 풀면 ... 백준그래프탐색그래프탐색 <BOJ>10026번: 적록색약 BFS 코드 틀을 알고 있으면 쉽게 풀 수 있는 전형적인 BFS 문제이다. 현재 좌표와 다음 좌표의 색상이 같으면 이동하는 방식으로 탐색한다. 2중 for문으로 방문하지 않은 좌표인지 파악해서 해당 좌표에서 BFS를 호출한다. 이 때 카운팅을 한다. → 각 색상별로 영역이 몇 개인지 파악함 적록색약인 경우를 위해 G영역을 R영역으로 바꾸고, visited를 초기화 한 뒤 다시 탐색한다.... pythonBFSboj너비우선탐색그래프탐색그래프백준BFS 7562번 나이트의 이동 파이썬 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l ×... 백준BFS알고리즘그래프탐색BFS <BOJ>7562번: 나이트의 이동 BFS의 틀을 알면 바로 풀 수 있는 문제 중의 하나다. dx[], dy[]로 나이트의 이동 방향을 미리 초기화 한다. Flood Fill을 통해 목표 지점까지의 거리를 계산하면 된다.... Java그래프그래프탐색BFS너비우선탐색boj백준BFS