문제 출처 : https://www.acmicpc.net/problem/2667
사고과정
오랜만에 문제를 풀어서 뇌정지가 와서 너무 오래 걸렸다.. 이전에 풀었던 문제와 동일한 유형의 그래프 탐색 단지 좀 더 효율적으로 풀 수는 있을듯.
처음에는 문제를 보고 "전체적인 맵 탐색은 BFS로 아파트 단지를 세기 시작할때는 DFS로 하면 효율적이겠다!" 라는 생각을 했다. ( 이전 문제들에 대한 학습 때문인지 넓은 범위를 스캐닝할 때면 BFS가 효율적일것 같고 한 부분의 전체를 조사하는 것이면 DFS가 효율적일 것 같다. 실제로 이 문제에서 맵을 스캐닝 하는 건 BRUTE FORCE )
하지만 여러 문제들에 봉착했다.
지나간 곳을 표시하여 가지치기를 할수가 있을까? ( 그렇다면 주변에 탐색한 곳만 있다면 더이상 전진 불가 )
queue를 이용하여 BFS로 맵을 탐색하고 싶은데... 무한 루프가 돌게 된다.
위에처럼 0을 만나면 QUEUE에 추가한다 했을 때 계속 해서 무한 루프를 돌게 된다.
BFS는 node의 link들을 이용하여 next_node로 이동하며 level 단위로 탐색하는 기법이다.
하지만 이 문제에서는 정확하게 next_node에 대한 방향이 정해져있지 않다. 그렇기 때문에 전 방향에 대한 조회를 실시해야 하며 이전에 1->0인 부분을 다시 조회하는 과정이 발생해 무한루프를 돌게 된다.
if) 이미 지나온 부분은 다시 조회하지 않게끔 방향성을 정해주고 조회를 한다면? by 2
여기서도 문제 발생! 어떤 노드를 탐색할려하는데 주변이 모두 조회해버려서 갇혀버린다면?
더이상 탐색 불가한 상황이 되어버린다.
import sys
from collections import deque
N = int(sys.stdin.readline().rstrip("\n"))
a_map = [list(map(int,sys.stdin.readline().rstrip("\n"))) for _ in range(N)]
apartment =[]
a_q = deque([[0,0]])
dic = [[-1,0],[0,1],[1,0],[0,-1]]
def dfs (x,y,count) : # count하여 단지수 추가
for i in range(4) :
n_x, n_y = x+dic[i][0],y+dic[i][1]
if n_x>=0 and n_x<=N-1 and n_y>=0 and n_y<=N-1 :
if a_map[n_x][n_y] == 1 :
a_map[n_x][n_y] = 0
dfs(n_x,n_y,count)
return count+1
while a_q :
now = a_q.popleft()
for i in range(4) :
c=0
nx, ny = now[0]+dic[i][0],now[1]+dic[i][1]
if nx>=0 and nx<=N-1 and ny>=0 and ny<=N-1 :
if a_map[nx][ny] == 0 :
a_q.append([nx,ny])
continue
elif a_map[nx][ny] == 1 :
a_map[nx][ny]=0
apartment.append(dfs(nx,ny,c))
else : #out of index range
continue
print(len(apartment))
apartment.sort()
for n in range(len(apartment)) :
print(apartment[n])결국 해결 불가, 이전 문제를 참고해보니까 이렇게 풀면 똑같이 되겠는데...? 이전 문제(양배추)처럼 심플하게 가자.
import sys
from collections import deque
N = int(sys.stdin.readline().rstrip("\n"))
a_map = [list(map(int,sys.stdin.readline().rstrip("\n"))) for _ in range(N)]
apartment =[]
a_q = deque([[0,0]])
dic = [[-1,0],[0,1],[1,0],[0,-1]]
def dfs (x,y,count) : # count하여 단지수 추가
for i in range(4) :
n_x, n_y = x+dic[i][0],y+dic[i][1]
if n_x>=0 and n_x<=N-1 and n_y>=0 and n_y<=N-1 :
if a_map[n_x][n_y] == 1 :
a_map[n_x][n_y] = 0
count=dfs(n_x,n_y,count)
return count+1
for h in range(N) :
for w in range(N) :
if a_map[h][w]==1 :
a_map[h][w] = 0
apartment.append(dfs(h,w,0))
print(len(apartment))
apartment.sort()
for n in range(len(apartment)) :
print(apartment[n])조금 더 효율적으로 짤 수 있을 것 같은데 꼭 이중 for문을 사용해서 맵을 탐색하여야만 하는가? 지나간 visited를 다시 보지 않게 한다면 좀 더 효율적일 것 같은데 (어차피 map의 전체를 조회하니까 의미없나)
결국 deque 제거하니 시간 더 빨라짐 deque가 생성하는 것 자체로 시간 복잡도가 조금 높아지는 것 같다.
그래프 탐색은 이중 for문을 이용해 전제 map을 조회하는 방식 말고는 없을까??
