BOJ 9205(맥주 마시면서 걸어가기)

풀이(BFS)

- 플로이드 와샬 혹은 BFS 문제이다.

- 이웃한 점을 기준으로 서로간에 이동이 가능하면, 그래프를 정의해주는 것이 핵심이다.

 

즉, 아래와 같이 조건을 만족할 경우 그래프를 그려준다.

   point = [ list(map(int, input().split())) for _ in range(n + 2) ]
   edges = [[] for _ in range(N + 2)]
   #adjM = [[0] * (n + 2) for _ in range(n + 2)]
    
    for i in range(N + 2):
        for j in range(N + 2):
            if i == j: continue
            if abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) <= 1000:
                edges[i].append(j)
                '''
                or
            	adjM[i][j] = 1
                adjM[j][i] = 1
            	'''

문제에 나온 상황 그대로 Arr[65535][65535] 배열을 만들려고 하면 안된다.

 

from sys import stdin
from collections import deque
input = stdin.readline

def bfs():
    vis = [0 for _ in range(n + 2)]  # 방문 여부 표현
    de = deque()
    de.append(0)
    vis[0] = 1

    while len(de) != 0:
        cur = de.popleft()
        for i in range(n + 2):
            if adjM[cur][i] == 1 and vis[i] == 0:
                de.append(i)
                vis[i] = 1
    if vis[n + 1]:
        print("happy")
    else:
        print("sad")


t = int(input())
for _ in range(t):
    n = int(input()) # 편의점 갯수
    point = [ list(map(int, input().split())) for _ in range(n + 2) ]
    adjM = [[0] * (n + 2) for _ in range(n + 2)]

    # 거리가 1000이내로 이동이 가능하면 인접 행렬에 포함
    for i in range(n + 2):
        for j in range(n + 2):
            if i == j: continue
            if abs(point[i][0] - point[j][0]) + abs(point[i][1] - point[j][1]) <= 1000:
                adjM[i][j] = 1
                adjM[j][i] = 1

    bfs()

---

풀이(Floyd Warshall)

void solve(int N){
    for(int k = 0; k < N + 2; k++){
        for(int i = 0; i < N + 2; i++){
            for(int j = 0; j < N + 2; j++){
                if(i==j) continue;               //Optimized
                if(i==k || j==k) continue;       //Optimized       
                
                if(adjM[i][j] == true) continue;
                
                if(adjM[i][k] && adjM[k][j])  // [핵심]연결되어 있지 않지만, 건너서 갈수 있다면,
                    adjM[i][j] = true;        // 연결된 것으로 본다.
            }
        }
    }
    if(adjM[0][N + 1]) cout << "happy" << "\n";
    else cout << "sad"<<"\n";
}

---

알게된 부분

아래와 같이 solve()를 함수로 두면, adjM과 같은 인자가 bfs로 공유되지 못한다.

반면에 solve() 부분을 밖으로 빼면(즉, 함수로 두지 않으면), adjM가 공유가 가능하다.

전역 변수로 잡히는가 보다.

from sys import stdin
from collections import deque
input = stdin.readline

def bfs(n, de, adjM, vis):
    while len(de) != 0:
        cur = de.popleft()
        for i in range(n + 2):
            if adjM[cur][i] == 1 and vis[i] == 0:
                de.append(i)
                vis[i] = 1

def solve():
    t = int(input())
    for _ in range(t):
        de = deque()
        n = int(input()) # 편의점 갯수
        point = [ list(map(int, input().split())) for _ in range(n + 2) ]
        adjM = [[0] * (n + 2) for _ in range(n + 2)]
        vis = [0 for _ in range(n + 2)] # 방문 여부 표현

        # 거리가 1000이내로 이동이 가능하면 인접 행렬에 포함
        for i in range(n + 2):
            for j in range(n + 2):
                if i == j: continue
                if abs(point[i][0] - point[j][0]) + abs(point[i][1] - point[j][1]) <= 1000:
                    adjM[i][j] = 1
                    adjM[j][i] = 1

        de.append(0)
        vis[0] = 1
        bfs(n, de, adjM, vis)
        if vis[n + 1]:
            print("happy")
        else:
            print("sad")
solve()