안녕하세요! 큰돌님. 문제를 풀다가 자꾸 visited 배열에 오버플로우가 일어나는 것 같아서 예시 코드와 비교해 봤더니, 큰돌님은 max_n = 104로 배열의 크기를 최대로 정의 해 놓으셨더라구요.그래서 큰돌님 처럼 다음과 같이 배열의 크기를 최대로 해놓고 하니, 문제가 해결되었습니다.const int max_n = 104;저는 입력받는 코드를 따로 만들지 않아서, 크기를 예측할 수 있는 코드여서 5X5 로 정의를 해놓았는데, 왜 오버플로우가 일어나는 지 궁금합니다! 제가 작성했던 코드 첨부하겠습니다.// Online C++ compiler to run C++ program online #include <bits/stdc++.h> using namespace std; const int max_n = 104; int dy[4] = {-1, 0, 1, 0}; int dx[4] = {0, 1, 0, -1}; int main() { int N = 5; int M = 5; int x,y; int visited[N][M] = {0,}; //방문 노드 //시작 지점 int sx = 0, sy = 0; //끝 지점 int ex = 0, ey = 4; //MAP int map[N][M] = { {1,0,1,0,1}, {1,1,1,0,1}, {0,0,1,1,1}, {0,0,1,1,1}, {0,0,1,1,1} }; queue<pair<int, int>> q; //깊이 탐색을 위한 큐 visited[sy][sx] = 1; // start 위치 방문 처리 q.push({sy,sx}); while(q.size()) { tie(y,x) = q.front(); q.pop(); for(int i = 0; i < 4 ; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if(ny < 0 || ny >= N || nx < 0 || nx >= M || map[ny][nx] == 0) continue; if(visited[ny][nx]) continue; visited[ny][nx] = visited[y][x] + 1; q.push({ny, nx}); } } printf("%d\n", visited[ey][ex]); // 최단거리 디버깅 for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cout << visited[i][j] << ' '; } cout << '\n'; } return 0; }

고민해보았지만, 제 코드가 왜 시간초과 나는지 이유를 알 수 없어서, 답답한 마음에 질문드립니다.[시간 복잡도]- 각 좌표 정보 얻기 위한 이중포문 10^6- visit 이차원 배열 2개 생성 2*10^3- bfs1 10^6(최대)- bfs2 10^6(최대)- 총 3*10^6 + 2*10^3- 위처럼 계산하면 시간 초과가 발생하지 않아야 하나, 발생하며- 위에 적은 것에서 bfs2는 우선순위큐를 사용하기에 더더욱 연산횟수가 줄어들것이라 생각하였습니다. 왜 시간 초과가 발생한 걸까요ㅠimport sys input = sys.stdin.readline from collections import deque import heapq d = [(0,1),(0,-1),(1,0),(-1,0)] # 영희 시작점 -> 산딸기 전체 탐색 def bfs1(): q = deque([(sx,sy)]) visit1[sx][sy]=1 while q: x,y = q.popleft() for dx,dy in d: nx = x + dx ny = y + dy if 0<=nx<N and 0<=ny<M and visit1[nx][ny]>visit1[x][y]+1 and arr[nx][ny]!=1: visit1[nx][ny]=visit1[x][y]+1 q.append((nx,ny)) # 각 산딸기 -> 기사 # 우선순위큐를 활용, 어느 산딸기 위치에서 시작하든 최단 거리로 도달할 수 있도록 def bfs2(): h = [] for x,y in raspberry: heapq.heappush(h,(visit1[x][y]-1, x,y)) visit2[x][y]=visit1[x][y]-1 while h: dist, x, y = heapq.heappop(h) if visit2[x][y]<dist: continue if (x,y)==(ex,ey): return dist for dx,dy in d: nx,ny = x + dx,y+dy if 0<=nx<N and 0<=ny<M and arr[nx][ny]!=1 and visit2[nx][ny]>dist+1: visit2[nx][ny] = dist+1 heapq.heappush(h,(dist+1,nx,ny)) # 입력 M,N = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] sx,sy,ex,ey=0,0,0,0 raspberry = [] for i in range(N): for j in range(M): if arr[i][j]==2: sx,sy = i,j elif arr[i][j]==3: ex,ey = i,j elif arr[i][j]==4: raspberry.append((i,j)) visit1 = [[float('inf')]*M for _ in range(N)] visit2 = [[float('inf')] * M for _ in range(N)] bfs1() print(bfs2())

안녕하세요. 궁금한점이 있어서 질문드립니다.BFS를 풀다가 생각난건데OOOXXXXOOOOXXXXXXXXXOOOOO이렇게 배열이 들어왔을때 1112233111433333333355555이런식으로 영역별로 숫자가 1씩 증가되는코드를 작성하고 싶은데 어떻게 해야할까요..?

 강사님 안녕하세요! 토마토 문제 강의 듣다가 질문이 있어서 문의 드립니다.강의 내용 9:56 부분에서dis 부분에 (2,4) 부분이 3 이 아니라2가 되어야 하지 않나 싶어서 질문드립니다!이유는 level 1 - (2,5)에서 level 2가 될때 (2,4)가 2일 차에 토마토가 익어서 그렇게 될거 같은데,제가 이해를 잘못하고 있는 것인지 알 수 있을까요?

안녕하세요 강사님, 강의를 듣다가 동전 문제를 BFS로 풀 수 있을거 같아 이렇게 풀었는데, 괜찮은 코드인지 여쭤보고 싶습니다.   import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { static int N, M, count; static int[] arr; static Queue<Integer> queue = new LinkedList<>(); public void input() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); arr = new int[N]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) { arr[i] = Integer.parseInt(st.nextToken()); queue.offer(arr[i]); } st = new StringTokenizer(br.readLine()); M = Integer.parseInt(st.nextToken()); } public int BFS() { while (!queue.isEmpty()) { count++; int len = queue.size(); for (int i = 0; i < len; i++) { int value = queue.poll(); for (int X : arr) { int data = value + X; if (data == M) return count+1; // 동전의 값을 Queue에 삽입 전에 체크하기 때문에 +1를 추가해서 리턴 if (data < M) queue.offer(data); } } } return count; } public static void main(String[] args) throws Exception { Main main = new Main(); main.input(); System.out.println(main.BFS()); }}

dx=[0,1,0,-1] dy=[-1,0,1,0] n = int(input()) board = [ [0]*n for i in range(n) ] dq = deque() MAX = -999 MIN = 999 cnt = 0 for i in range(n):  # 한 줄씩 입력 받기     tmp = list(map(int,input().split()))     for j in range(n):         board[i][j] = tmp[j]         if tmp[j] < MIN :             MIN = tmp[j]             sx =i             sy =j             dq.append([sx,sy])         elif tmp[j]>MAX:             MAX = tmp[j]             ex = i             ey = j while dq:     tmp = dq.popleft()             #     if tmp[0] == ex and tmp[1]==ey:                     cnt+=1                     for a in range(4):         X = dx[a]+tmp[0]         Y = dy[a]+ tmp[1]         if 0<=X<n and 0<=Y<n and board[X][Y] > board[tmp[0]][tmp[1]]   :                     # board[X][Y] = 0             dq.append([X,Y])                         print(cnt)       ''' 해당 코드에서 뭐가 잘못된건지 집어주시면 감사하겠습니다. '''

BFS를 이용하여 미로의 최단거리를 구하는 방식이   1. 일단 갈 수 있는 좌표(맵의 모든 초록색 점)를 BFS로 탐색해 모두 저장한 다음, 2. 도착점(23, 23)을 기준으로 parent만 따라가면서 플레이어가 이동할 좌표를 _points 리스트에 저장한 후(어차피 역순으로 parent를 찾으면서 가게 되면 막혀있는 길로 갈 필요가 없으므로) 3. _points의 순서를 뒤집어서 시작점부터 출발하게 하면 플레이어가 최단거리로 도착점까지 간다   이렇게 이해하는 게 맞을까요?

제가 2일 동안 고민해봤고 선생님의 논리와 같은 거 같은데 왜 안 풀리는지 모르겠습니다. 숨바꼭질2에서는 답이 잘 나와서 확인 해봤는데  (방금 고민하면서 문제 풀어버렸습니다. 그렇지만 질문은 있습니다.) //cout << s <<" "; 이거 있는 부분을 해제하고 실행하면 괴상한 수를 잔뜩 거쳐서 목적지로 가더라고요. 이거 제 머리속에 있는 bfs 논리로는 괴상한 수들을 거칠 이유가 없습니다.   또 우선 dfs를 이용해서 경로 추적할 수 있을 거 같은데 그 방향은 안 되는 건가요?     #include<bits/stdc++.h> using namespace std; #define INF 987654321 int n, k, ret = INF, cnt; const int jump[] = {-1, 1, INF}; int visited[100004]; int parent[100004]; void printPath(int i){ if(parent[i] == -1){ return; } printPath(parent[i]); cout << i << " "; }     void bfs1D(int s){ visited[s] = 1; queue<int> q; q.push(s); int ns =-1; parent[s] = -1; while(!q.empty()){ int here = q.front(); q.pop(); //cout << s << " "; if(here==k){ cnt++; ret = visited[here]-1; break; } for(int i=0;i<3;i++){ if(i==2){ ns = 2*here; }else{ ns = here + jump[i]; } if(ns <0 || ns >100000) continue; if(visited[ns]==0){ visited[ns] = visited[here]+1; q.push(ns); parent[ns] = here; } } } cout << ret << '\n'; cout << s << " "; printPath(k); }     int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >>k; bfs1D(n);   }

안녕하세요:) 중요한건 아니지만 승환이가 (0, 0)부터 출발하므로 답은 9-1=8이 아닌가요?

안녕하세요 강사님 BFS를 이용해서 답안을 작성해보았는데요, 어딘가가 잘못된 것 같은데 잘 모르겠네요ㅜㅜ 제가 작성한 코드는 다음과 같습니다. N = int(input()) apt = [] for _ in range(N): tmp = [] for i in input(): tmp.append(int(i)) apt.append(tmp) res = [] q = deque() for r in range(N): for c in range(N): if apt[r][c] == 1: cnt = 1 q.append((r,c)) while q: x, y = q.popleft() # (x,y) 좌표 방문 apt[x][y] = 0 # 방문한 곳은 0으로 변환 for i, j in ((x+1,y), (x,y+1), (x-1,y), (x,y-1)): if i >= 0 and i <= N-1 and j >= 0 and j <= N-1: # 좌표값이 제약조건을 만족할 경우 if apt[i][j] == 1: # 문제 조건을 만족하는지 확인 cnt += 1 q.append((i,j)) res.append(cnt) print(len(res)) for i in sorted(res): print(i)   위와 같이 작성했고 1번 input으로 답을 확인해보면 단지 갯수는 4개, 각 단지의 아파트 수는 3, 5, 10, 28이 나옵니다. 그런데 답은 3, 5, 10, 22인걸 보니 마지막 단지만 어딘가 잘못 카운트 한 것 같네요. 다른 input들도 확인해보니 다 제일 큰 단지 값만 잘못 나옵니다. 어떤 부분이 잘못된걸까요?ㅜㅜ

dis[6][6]에 도달할 수 있는 경우가 한가지가 아니라 여러갈래에서 도착 지점으로 갈 수 있는데 마지막으로 dis[6][6]에 들어간 값이 어떻게 최단 경로인건지 궁금합니다.

안녕하세요 선생님. 항상 질 좋은 강의 감사드립니다. 다름이 아니라 다음과 같이  코드를 작성했는데, 괜찮은 코드인지 여쭤보고 싶습니다. 그리고 강의 코드에서 조건문에 `nv>0 && nv<=10000`와 같이 작성한 코드는 입력으로 주어진 시작지점에서 도착지점을 찾지 못할 때를 방어하려고 작성한건지 궁금합니다. let s = 5; let e = 14; console.log(solution(s, e)); function solution(s, e){ let queue = []; let visited = Array.from({length: e}, () => 0); queue.push([s, 0]); visited[s] = 1; while (queue.length){ let [v, time] = queue.shift(); if (v === e) return time; for (let nv of [v+1, v-1, v+5]){ if(!visited[nv] && nv>0 && nv<=10000){ visited[nv]=1; queue.push([nv, time+1]); } } } }    

미로의 최단거리 통로 문제를 먼저 보고 풀고 성공하고 나서 강사님 강의에 나오는 코드를 보니 저와는 조금 다른데 제 코드와 비교해서 강사님 코드가 더 효율적일까요? 코드 짜는 방식을 강사님 식으로 짜는 걸로 연습을 해야 할지 아니면 제 방식으로 비슷한 문제를 풀어나가도 되는지 아니면 추후에 강사님 식으로 푸는 게 나중에 응용이나 활용 문제 나왔을 때 더 좋은가 궁금합니다. 제 코드 피드백 좀 부탁드리고 싶습니다. 매번 감사드립니다! ```java import java.util.*; public class MazeSearch2 {     public static int[][] map = new int[7][7];     public static int ans = 0;     public static int[] arrX={0,0,1,-1};     public static int[] arrY = { 1, -1, 0, 0 };     public static void main(String[] args) throws Exception {         Scanner sc = new Scanner(System.in);         for (int i = 0; i < 7; i++)              for (int j = 0; j < 7; j++)                  map[i][j] = sc.nextInt();         map[0][0] = 1;         System.out.println(solution(0, 0));     }     public static int solution(int x, int y) {         Queue<Integer> q = new LinkedList<>();         q.add(x);         q.add(y);         while (!q.isEmpty()) {             int len = q.size()/2;             for (int i = 0; i < len; i++) {                 int xx = q.poll();                 int yy = q.poll();                 for (int j = 0; j < 4; j++) {                     if (xx + arrX[j] < 7 && yy + arrY[j] < 7 && xx + arrX[j] >=0 && yy + arrY[j] >=0) {                         if (map[xx + arrX[j]][yy + arrY[j]] == 0) {                             if (xx+arrX[j] == 6 && yy+arrY[j] == 6)                                 return ans+1;                             map[xx + arrX[j]][yy + arrY[j]] = 3;                             q.add(xx + arrX[j]);                             q.add(yy + arrY[j]);                            }                     }                 }             }             ans++;         }         return -1;     } } ```

두 갈래 이상 나뉘어진 구간(길이가 같다면)에서는 어떻게 판단하고 나아가는지 이해가 되지 않아 구글링을 좀 해봤는데 두 갈래로 나뉘어져 있는 구간은 큐에서 두 좌표를 모두 큐에 넣고 큐에서 하나씩 꺼내 그 지점과 근접한 방문하지 않은 지점을 방문하게 된다는데  글이 있더라구요 이 말이 알 것 같으면서도 잘 이해가 되지 않습니다. 두 갈래에서는 어떻게 판단하고 앞으로 나아가나요? 그냥 두갈래중 먼저 발견한 정점으로 가는 건가요? 파란점이 시작점이라고 할때 만약 위 오른쪽 아래 왼쪽 순서로 for문을 돌면 오른쪽 점을 먼저 발견하니까 오른쪽으로 가게되고 결국 막히게 되는데  일단 오른쪽으로 계속 이동하다가 막히게 되면  다음으로 갈 수 있는 아래쪽 점으로 이동하고 이런식으로 반복하여 최단경로를 찾게 되는건가요?