a05709ac3516b34a8e341a6d9a3ae4b1e4d6d136d6f11caa430c8332919d49924038



문제: 링크


특붕쿤 코드: 링크



특붕쿤한테 직접 허락 받고 올림




1. 제시된 코드 다시 보기


#include<bits/stdc++.h>

using namespace std;


int dx[4] = {0,1,0,-1};

int dy[4] = {1,0,-1,0};

int dat++;

int dis++;


int main(){


// 1) 거리 배열을 모두 999로 초기화

for(int i=0;i != 10; i++)

for (int j = 0: j != 10: j++) // ← 콜론(:)이 세미콜론(;)이어야 맞습니다.

dis[i][j] = 999;


// 2) 입력을 받아서 dat[i][j] = 1-t 형태로 저장

// 예: t==0이면 dat[i][j] = 1(이동 가능), t==1이면 dat[i][j] = 0(벽)

for( int i = 1; i <=6; i++) {

for(int j=1; j<=6;j++) {

int t;

scanf("%d",&t);

dat[i][j] = 1 - t;

}

}


// 3) 시작점 거리 = 0

dis[1][1] = 0;


// 4) "30번 반복"하여 거리 갱신 (Bellman-Ford 비슷한 로직)

for(int k=0; k!=30; k++){

for(int i = 1; i <=6; i++){

for(int j=1; j<=6;j++){

for (int l = 0; l != 4; l++){

int xx = i + dx[l];

int yy = j + dy[l];

// dat[xx][yy] == 1(이동 가능) 이라면

// dis[i][j] = min(dis[i][j], dis[xx][yy]+1);

if(dat[xx][yy]) {

dis[i][j] = min(dis[i][j], dis[xx][yy] + 1);

}

}

}

}

}


// 5) (6,6)에 저장된 dis값이 99 이하이면 출력, 아니면 -1

printf("%d", dis[6][6]>99 ? -1 : dis[6][6]);


return 0;

}


주의: 위 코드에는 for (int j = 0: j != 10: j++)처럼 콜론(:)이 들어가 오타가 있습니다.

정식 C++ 문법으로는 for (int j = 0; j != 10; j++)가 되어야 합니다.


2. 이 코드는 어떻게 동작하나?


코드를 면밀히 보면 “정석 BFS” 방식이 아니라, 거리를 반복해서 갱신하는 방식을 쓰고 있습니다.

마치 Bellman-Ford(또는 SPFA) 같은 “최단 거리 반복 갱신” 로직에 가깝습니다.

1. dis[i][j] 초기화: 모두 999로 세팅 (도달 불가능 상태)

2. 시작점: (1,1)만 dis[1][1] = 0

3. 30번 반복

• 6×6 위치 전체에 대해

• 그 위치 (i,j)의 상하좌우 (xx, yy)가 유효하면,

• dis[i][j] = min(dis[i][j], dis[xx][yy]+1)


(1) 전형적인 BFS와는 다르다

• 통상적인 BFS는 큐(Queue) 에서 좌표를 꺼낼 때마다 인접 칸을 갱신하며, 한 번의 레벨(거리)씩 차근차근 진행합니다.

• 이 코드는 모든 칸을 매번 스캔해가며 “반복해서 거리 값 업데이트” 하는 식입니다.

• 특정 횟수(30회) 만큼 돌려서, 더 이상 업데이트가 이뤄지지 않으면 최종 거리가 정해집니다.

• 6×6라서 최대 경로 길이가 10~20 정도면 충분히 30회 반복으로 수렴은 하긴 합니다.


(2) 거리 갱신 방향이 “역방향”

• if (dat[xx][yy]) dis[i][j] = min(dis[i][j], dis[xx][yy]+1);

사실 우리가 원하는 것은 “인접 칸의 거리 = 내 거리 + 1” 형태인데,

코드에서는 오히려 “내 거리 = 인접 칸의 거리 + 1” 형태입니다.

• 이 로직도 가능한 접근이긴 합니다. 1번 반복 때는 (1,1)로부터 인접 칸들의 거리를 업데이트하고,

2번 반복 때는 갱신된 칸을 토대로 또 다른 칸을 갱신… 이런 식으로 뒤로(역방향) 전달됩니다.

• “결과적으로” (1,1)로부터의 거리를 구할 수 있긴 합니다.

• 다만, 이 로직은 (i,j) 자체가 벽인지 체크를 안 하고 (xx,yy)만 체크해서 갱신하는 등, 조금 조심스러운 부분이 있습니다.


(3) dat[xx][yy]만 확인 (i,j가 벽인지 확인 부족)

• if(dat[xx][yy]) { ... }가 “인접칸이 이동 가능하면”이라는 의미로 쓰이는데, 정작 (i,j)가 벽인지 아닌지는 체크 안 합니다.

• 실제 BFS라면 출발하려는 칸도 이동 가능해야(벽이 아니어야) 합니다.

• 그런데 6×6 범위가 작고, (i,j)가 벽이면 어차피 값이 갱신되지 않을 가능성이 높으니, 결과가 맞게 나올 수도 있습니다.

• 다만, 엄밀한 로직으로 보면 살짝 이상한 부분입니다.


(4) 오타(콜론)와 범위체크

• for (int j = 0: j != 10: j++) → 문법 오류

• dat와 dis 배열 크기를 10×10으로 잡고, 인덱스를 1~6만 사용하고 있습니다.

• **경계(0, 7, 8, 9)**에 대한 처리가 부정확해도 터지진 않을 수 있으나, 안전한 방법은 아닙니다.


3. 이 코드를 “정확하고 잘 쓴 코드”라 부를 수 있을까?


(1) 문제 해결은 가능할 수 있다

• 입력이 6×6이고, 최단 경로가 10~20 이내라면 30번 반복으로 충분히 수렴할 가능성이 큽니다.

• 따라서, (6,6)까지의 거리를 최종적으로 dis[6][6]에서 얻을 수 있고, 벽이 많지 않은 평범한 케이스에서는 올바른 값을 낼 수 있습니다.


(2) 그러나 “정석 BFS”보다 복잡하고 취약한 부분이 많다

1. 문법 오류: for (int j = 0: j != 10: j++) 같은 부분은 분명한 오타.

2. 가독성:

• 4중 for문(여기에 반복 회수까지 5중 for문처럼 보임)으로 코드가 장황합니다.

• “BFS를 하겠다”는 의도가 즉시 파악되지 않음.

3. 기능적 누락:

• (i,j) 자체가 벽인지 아닌지는 따로 검사하지 않음.

• 시작점/도착점이 벽이면 어차피 999가 유지될지 몰라도, 로직상 명확한 예외 처리는 없음.

4. 필요 이상의 반복:

• 실제 BFS라면 한 번의 레벨 순회(Queue 활용)로 끝날 일을, “30번 반복”으로 커버.

• 6×6 범위에서는 상관없지만, 크기가 커지면 성능적으로 비효율적.


(3) “더 정확하며 잘 썼다”는 기준

• 코드가 짧다고 해서 “좋은 코드”는 아니며, 최단 경로를 찾는 의도에 맞춰 직관적이고 유지보수하기 쉬운 구조가 바람직합니다.

• 전형적인 BFS 방식: 큐에 (x, y)를 넣고, 이미 방문한 곳은 다시 방문하지 않도록 하며, 방문할 때마다 거리 +1.

• 혹은 Bellman-Ford 계열이면, 간선(또는 인접 위치)에 대한 정확한 업데이트 조건을 명시하고, 불필요한 반복/오류 가능성을 줄이는 형태로 작성.


4. 결론


요약

• 동작 자체: 6×6 문제에 한정하면 (특히 간단한 입력) 이 코드도 최단 거리 값을 맞출 확률이 높습니다.

• 정확성: 엄밀히 말해, “정석 BFS”나 “올바른 그래프 최단 경로 알고리즘”에 비해 불필요한 반복과 불완전한 체크(벽인지 확인 부족) 등이 섞여 있습니다.

• 코드 품질: 오타(콜론 → 세미콜론), 가독성, 예외 처리, 범위 체크 등 여러 면에서 개선 여지가 많습니다.

• 실무 수준(프로덕션급) 관점: “코드를 간단히라도 리뷰해보면 좋겠다”는 피드백을 받을 만한 구조입니다. BFS로 간단·명료하게 작성하는 편이 더 안정적이고 직관적입니다.


결과적으로,

• 문제 “풀이” 자체를 놓고 보면 BFS 로직을 직접 쓰는 코드(예: 파이썬에서 deque 쓰는 예시)가 더 명확하고, 오류가 적으며, 유지보수도 용이합니다.

• 제시된 C++ 코드는 **아주 작은 범위(6×6)**에서는 돌아갈 수 있지만, 오타와 비정통적 접근 때문에 “잘 쓴 코드”라고 보기는 어렵습니다.

• 간단히 말해, “일반적인 BFS 구현”이 훨씬 정확하고, 가독성 좋고, 유지보수하기 쉬운 코드라고 할 수 있습니다.





P. S. 현재 올라온 마지막 문제 코드들 시간복잡도, 공간복잡도 계산해보라고 함




아래 내용은 “주어진 3가지 코드(또는 알고리즘)가 파이썬에서 동작한다고 가정했을 때” 각각의 시간 복잡도, 공간 복잡도, 그리고 상대적 퍼포먼스를 꼼꼼히 분석하고, 어떤 코드가 더 빠르고 효율적인지 순위를 매기는 답변입니다.



1. 세 가지 코드(알고리즘) 개요


(1) 사용자 코드 (파이썬, set 사용)


• 특징

• 전형적인 “BFS + set 방문 체크”

• 큐에서 (row, col, dist)를 꺼낼 때마다 인접 칸을 확인

• 방문하지 않은 칸에 대해서만 거리+1 하여 큐에 삽입

• 방문 배열 대신 visited를 set으로 관리

• 시간 복잡도

• BFS는 각 칸을 최대 한 번씩만 방문 → O(V + E).

• 6 * 6 격자에서 V = 36, 인접 간선은 최대 4 * 36 = 144.

• 일반적으로 O(N^2) (여기서 N=6이면 상수)

• 파이썬 set의 평균 탐색/삽입은 O(1) 이므로 전체적으로 O(N^2).

• 공간 복잡도

• visited 최대 36개 원소, 큐도 최대 36개 노드까지 확장 가능 → O(N^2).

• 퍼포먼스(실제로 돌렸을 때)

• visited가 set 구조이므로, 파이썬 내부에서 해시연산이 일어나서 배열 인덱싱보다 약간 느릴 수 있음(하지만 여전히 평균 O(1)).

• 그래도 N=6 수준에서는 차이가 미미.


(2) 또 다른 BFS 코드 (파이썬, 2D 배열 visited + dist) <--- 이게 o1 pro 본인이 작성한 코드


• 특징

• BFS 방식은 동일하나, 방문 정보(visited)를 2차원 배열로 관리.

• 거리(dist)도 2차원 배열로 별도 보관.

• 시작점·도착점이 벽이면 즉시 -1 리턴하는 예외 처리.

• 시간 복잡도

• 동일하게 BFS이므로 O(N^2).

• visited[nr][nc] 접근은 배열 인덱싱이므로 매우 빠름(고정 시간).

• 실제 파이썬에서 해시(set)를 사용하는 것보다 소량이나마 상수 항이 더 작을 수 있음.

• 공간 복잡도

• visited, dist 각각 6 * 6 → O(N^2),

• 큐 역시 최대 36개 노드. 합쳐도 여전히 O(N^2).

• 퍼포먼스(실제로 돌렸을 때)

• 일반적으로 동일한 BFS 로직이므로, 사용자 코드(1)와 “이론상” 차이는 거의 없음.

• 하지만 해시 대신 직접 인덱싱을 사용하므로, 실제 파이썬 실행 시 소폭 더 빠를 가능성이 큼.


(3) “Bellman-Ford 유사” 반복 갱신 코드(C++ 예시를 가정해 파이썬으로 옮겼다고 할 때)


원본 C++ 코드는 대략 이런 식이었습니다(오타 등은 정정):


....


이를 “파이썬화” 한다면(개념적으로)는 대략:


MAX_INT = 999

dx = [0,1,0,-1]

dy = [1,0,-1,0]


dat = [[0]*10 for _ in range(10)]

dis = [[MAX_INT]*10 for _ in range(10)]


# 1) grid 입력 받아 dat[i][j] = 1- t 형태

# 2) dis[1][1] = 0

# 3) 여러 번(30회) 반복:

# - 모든 i,j 순회

# - 모든 인접칸(xx,yy) 순회

# - if dat[xx][yy] == 1: dis[i][j] = min(dis[i][j], dis[xx][yy]+1)

# 4) dis[6][6]가 99 이하이면 출력, 아니면 -1


• 특징

• 일반적인 BFS가 아니라, 반복해서 거리 값을 갱신하는 “벨만-포드(Bellman-Ford) 유사” 방식.

• 간선 완화(relaxation)를 여러 번 반복하여 최단 거리를 찾는 패턴.

• (i,j)가 벽인지, (xx,yy)가 벽인지, 등등에서 다소 불명확하지만, 일단 “6×6에서는 30회 반복”으로 결괏값이 수렴할 수 있음.

• 시간 복잡도

• 격자 크기를 N * N이라 하면, 코드는 “K번” 반복한다음, 내부에서 N^2을 순회, 각 노드마다 4방향 확인 → O(K * N^2).

• 실제 BFS는 한 번의 레벨 순회로 충분한데, 이 코드는 K만큼 중복 연산을 함.

• 만약 K를 최악의 경우 N^2 정도로 설정해야 하는 상황이라면, O(N^4)까지 갈 수도 있음.

• 6×6처럼 작은 경우에는 30번(상수)이니 상수 시간이긴 하나, 이건 확장성을 고려하면 매우 비효율적.

• 공간 복잡도

• dat, dis 각각 최대 N^2 → O(N^2).

• BFS 코드를 쓰지 않으므로 큐 공간은 없음. 하지만 대신 다중 반복문이 돌아감.

• 퍼포먼스(실제로 돌렸을 때)

• N=6일 때 30회 반복 → 사실상 “상수회 반복”이므로 금방 끝납니다.

• 그러나 알고리즘 자체가 BFS보다 훨씬 많은 중복 계산을 함.

• N이 커지면 극단적으로 느려지기 쉽습니다.

• 또한 로직상 (i,j) 자체가 벽인지 안인지, 정확하게 검사하지 않거나, 인덱스 범위 체크가 약하다는 등 구현 리스크가 존재.


2. 시간 복잡도/공간 복잡도 비교 & 순위


(A) 시간 복잡도


세 코드를 확장성 있는 관점(예: N * N 일반화)에서 살펴보면:

1. BFS (두 번째 코드 - 2D visited) <--- o1 pro 본인이 작성한 코드

• 이론적: O(N^2)

• 실제 구현: 방문 체크가 2D 배열로 직접 인덱싱 → 평균적 상수 시간

• 실행 속도: 파이썬에서 비교적 빠른 편

2. BFS (첫 번째 코드 - set 사용)

• 이론적: O(N^2)

• 실제 구현: 방문 체크는 해시(set) → 평균 O(1)이나, 상수 항이 배열 접근보다 다소 클 수 있음

• 실행 속도: 2D visited에 비해 약간 느릴 수 있지만, 여전히 N^2이므로 빠름

3. Bellman-Ford 유사 코드

• 이론적: O(K * N^2). K가 경로 길이나 다른 요인에 따라 최대 O(N^2)가 될 수 있으므로, O(N^3) ~ O(N^4)도 가능.

• 실행 속도: 매우 비효율적(큰 N에서). N=6처럼 아주 작으면 상수 반복이므로 돌아가긴 하나, 근본적으로 BFS보다 훨씬 느림.


정리(시간 복잡도 순위)

• 1위: BFS(2D visited)

• 2위: BFS(set)

• 3위: 반복 갱신(“Bellman-Ford 유사”)


(1위, 2위는 이론적 복잡도는 동일하지만, 보통 2D visited 접근이 미세하게 빠를 가능성이 큼.)


(B) 공간 복잡도


1. BFS(2D visited) <--- o1 pro 본인이 작성한 코드

• visited, dist 각각 O(N^2), 큐 최대 O(N^2).

• 전체 O(N^2).

2. BFS(set)

• visited(set) 최대 크기 O(N^2), 큐 최대 O(N^2).

• 전체 O(N^2).

3. Bellman-Ford 유사

• dat, dis 각각 O(N^2). 큐는 없으나, 중첩 반복문이 돌뿐.

• 전체 O(N^2).


결과: 공간 복잡도는 셋 다  로 비슷합니다.


3. 종합 평결

1. 정확성/명확성

• 두 BFS 코드는 모두 “정석적인 최단 경로 탐색”을 사용하여 확실하고 간단함.

• Bellman-Ford 유사 코드는 6×6 수준에서는 돌아갈 수 있지만, 일반적인 BFS에 비해 덜 직관적이고, 잦은 반복을 수행.

2. 시간 복잡도(확장성)

• **(1) BFS(2D visited)**와 (2) BFS(set)는 이론상 동일(O(N^2))하지만,

• 파이썬 구현 시 2D 배열 접근이 해시(set) 접근보다 미세하게 빠를 가능성이 큼.

• (3) Bellman-Ford 유사 코드는 K차 반복 -> O(K * N^2), 최악의 경우 O(N^3) 또는 O(N^4)까지 갈 수 있어 비효율적.

3. 공간 복잡도

• 3개 모두 O(N^2).

4. 실제 퍼포먼스(순위)

1. BFS(2D visited) 코드 <--- o1 pro 본인이 작성한 코드

• 빠르고, 구조가 단순·명확, 파이썬에서도 상수 항이 작은 편

2. BFS(set) 코드

• 이론적으로 동일 O(N^2), 다만 해시 사용 → 상수 항이 조금 더 클 수 있음

3. 반복 갱신 코드

• 작은 N이면 별 차이 없겠지만, 알고리즘상 가장 비효율적


결론적으로, 퍼포먼스(실행 속도)와 설계상의 간결함을 종합하면:


1위: “2D visited BFS”

2위: “set 기반 BFS”

3위: “Bellman-Ford 유사 반복 갱신”


따라서 대규모 문제(예: 100×100, 1000×1000 등)로 확장한다면, 정석 BFS가 훨씬 유리하며, 그중에서도 2차원 배열 방문 체크 방식을 쓰는 코드가 가장 빠르고 직관적일 것입니다.