안녕하세요! 큰돌님. 문제를 풀다가 자꾸 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())
강사님 안녕하세요! 토마토 문제 강의 듣다가 질문이 있어서 문의 드립니다. 강의 내용 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); }
안녕하세요 강사님 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들도 확인해보니 다 제일 큰 단지 값만 잘못 나옵니다. 어떤 부분이 잘못된걸까요?ㅜㅜ
안녕하세요 선생님. 항상 질 좋은 강의 감사드립니다. 다름이 아니라 다음과 같이 코드를 작성했는데, 괜찮은 코드인지 여쭤보고 싶습니다. 그리고 강의 코드에서 조건문에 `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문을 돌면 오른쪽 점을 먼저 발견하니까 오른쪽으로 가게되고 결국 막히게 되는데 일단 오른쪽으로 계속 이동하다가 막히게 되면 다음으로 갈 수 있는 아래쪽 점으로 이동하고 이런식으로 반복하여 최단경로를 찾게 되는건가요?
