📝DFS + BFS : 개념
DFS + BFS : 예시로 이해하자
문제풀이
[S1]1697] 숨바꼭질
DFS와 BFS에 대해 학습하려고 서칭하던 중 어떤 작성자분이 본인은 둘 중 DFS를 더 선호하고, 둘 중 어떤걸로도 문제가 풀린다고 하는 블로그를 본 적이 있다. 그 블로그에서 DFS에 대해 학습하고, 아 나도 그럼 DFS만 사용해서 문제를 풀어볼까 싶은 생각이 들었고, 이 문제는 사실 보고 DFS로는 풀 문제가 아니라는 생각이 들었지만 DFS로 접근을 하였고, 실패하였다.
BFS에 대해 간단하게 공부를 하고 와서 풀어보았으나, 연결된 그래프 관계에서 큐를 이용해서 BFS방식으로 접근하는 것에 비해 직접 문제에 적용하려고 하니 생각보다 어렵게 생각되어 한참 고민을 하다 서칭을 하고 아이디어를 참고하였다.
애초에 내가 가장 고민했던 게 어떻게 -1, +1, 2를 구현할까 하는 생각이었는데 파이썬의 for문법을 사용하여 for value in (now-1, now+1, now2): 이렇게 표현할 수 있었다. 애초에 for문을 이렇게 사용할 것이라 생각 자체를 못해서 아쉽기보다 뭔가 아..이런 방법이 있었구나 하는 생각이 들었다.
또한 횟수를 기록하는 것도 어렵게 생각하고 있었는데, 애초에 BFS라는 것이 해당 높이에 해당하는 것들을 모두 계산하는 것이기 때문에 한 단계를 거칠수록 +1을 하는 형식으로 진행하면 되었다.
from collections import deque
def bfs():
q.append(cur)
# 큐가 남아있는 동안 계속
while(q):
# 큐에 값 빼기
now = q.popleft()
# 원하던 값을 찾은 경우
if(now == target):
print(cnt[now])
return
# 원하던 값이 아니라면 => | -1칸 | +1칸 | *2칸 |
for value in (now-1, now+1, now*2):
# 이미 지나친 값은 넘기고 아닌 값은 횟수 증가하고 큐에 넣자
if (0 <= value < MAX and cnt[value] == 0):
cnt[value] = cnt[now] + 1
q.append(value)
MAX = 100001 # 주어지는 값이 최대 10만
cur,target = map(int,input().split())
q = deque()
cnt = [0] * MAX
bfs()
[G5]7576] 토마토
순차적으로 접근하기 위해 애초에 토마토를 익힐 수 없는 구조를 제하고 dfs를 통해 토마토를 전부 익힐 수 있다는 가정하에 코드를 먼저 짰다.
정답에 가까워지자 (시도 1) : 원치 않는 결과값
오는데까지도 조금의 시행착오가 있었으나, 코드를 거의 다 완성했다. 일단 조금 곤란했던 게 큐에 저장을 하고 빼오면서 트리 탐색 형식으로 진행하고 싶었는데, 다른 것들과 달리 진행 상황 중에 횟수를 저장하기가 조금 까다로웠다. 이를 해결하기 위해서 큐에 추가는 나중에 한 번에 하고, 지금 큐에서 뽑을 수 있는 것을 다 뽑은 후에 큐를 한 번에 추가하는 형식으로 진행했다. 이 정도 코드까지 만들고 나서도 답이 제대로 나오지 않았고, 이해를 할 수 없어 print로 디버깅을 하다 큐에 값을 넣고 빼는 것에 문제가 생긴 것을 발견했다.
graph = []
queue = []
M,N = map(int, input().split())
for i in range(N):
graph.append(list(map(int, input().split())))
for i in range(N):
for j in range(M):
if(graph[i][j] == 1):
queue.append([i,j])
day = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
temp_queue = []
# 큐를 2개 만들어서 하나는 소비용, 하나는 다음꺼 저장용
while(any(0 in l for l in graph)):
day += 1
while queue:
cur = queue.pop()
# 상하좌우 판단
for i in range(4):
x = cur[0] + dx[i]
y = cur[1] + dy[i]
# 크기 안에서 & 0인 값 & 큐에 없는 값
if( (0<= x <= N-1 and 0<= y<= M-1) and graph[x][y] == 0 and [x,y] not in queue):
temp_queue.append([x,y])
graph[x][y] = 1
queue = temp_queue
print(graph, day)정답에 가까워지자 (시도 2) : 성공
뭔가 이상해서 출력을 해보니 분명 큐에서 팝을 했는데 빠져 나오지 않고 그대로 쌓이는 것은 물론 큐에 append하지 않은 것까지 추가되었다. 고민을 하다가 떠오른 것이 이 전에도 이런 오류가 있었고, 그 때도 지금처럼 너무나 큰 실수를 했다..
시도 3 : 시간초과
시도2에서 -1로 갇혀진 경우를 처음에 탐색하는 함수를 구현하고 나서 처음 시간초과를 받고 큐를 디큐로 바꿨는데도 시간이 초과가 나서 새로운 방법을 고민해야했다..
from collections import deque
import sys
input=sys.stdin.readline
# 그래프 탐색하면서 0인데 -1로 갇혀진 or 1인데 -1로 갇혀진
def corner_0():
for i in range(N):
for j in range(M):
if(graph[i][j]==0):
check = []
# 상하좌우 판단
for k in range(4):
x = i + dx[k]
y = j + dy[k]
if((0<= x <= N-1 and 0<= y<= M-1)):
check.append(graph[x][y])
if(0 not in check):
return 1
graph = []
q = deque([])
M,N = map(int, input().split())
for i in range(N):
graph.append(list(map(int, input().split())))
for i in range(N):
for j in range(M):
if(graph[i][j] == 1):
q.append([i,j])
day = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
#애초에 가둬진 토마토가 있다면 출력하고 끝
if(corner_0()):
print(-1)
else:
# 큐를 2개 만들어서 하나는 소비용, 하나는 다음꺼 저장용
while(any(0 in l for l in graph)):
temp_queue = deque([])
day += 1
while q:
cur = q.popleft()
# 상하좌우 판단
for i in range(4):
x = cur[0] + dx[i]
y = cur[1] + dy[i]
# 크기 안에서 & 0인 값 & 큐에 없는 값
if( (0<= x <= N-1 and 0<= y<= M-1) and graph[x][y] == 0 and [x,y] not in q):
temp_queue.append([x,y])
graph[x][y] = 1
q = temp_queue
print(day)시도 4 : 시간초과
from collections import deque
import sys
input=sys.stdin.readline
dx = [0,0,1,-1]
dy = [1,-1,0,0]
graph = []
q = deque([])
M,N = map(int, input().split())
for i in range(N):
graph.append(list(map(int, input().split())))
for i in range(N):
for j in range(M):
if(graph[i][j] == 1):
q.append([i,j])
day = 0
flag = 0
# 큐를 2개 만들어서 하나는 소비용, 하나는 다음꺼 저장용
while(any(0 in l for l in graph)):
if(not q):
falg = 1
break
temp_queue = deque([])
day += 1
while q:
cur = q.popleft()
# 상하좌우 판단
for i in range(4):
x = cur[0] + dx[i]
y = cur[1] + dy[i]
# 크기 안에서 & 0인 값 & 큐에 없는 값
if( (0<= x <= N-1 and 0<= y<= M-1) and graph[x][y] == 0 and [x,y] not in q):
temp_queue.append([x,y])
graph[x][y] = 1
q = temp_queue
if(flag==1):
print(-1)
else :
if(any(0 in l for l in graph)):
print(-1)
else:
print(day)😋 시도 5: 성공
문제가 되는 부분이 2개 있었다.
굳이 처음 시작할 때 0이 갇혀있나 확인할 필요가 없었다는 것과 굳이 현재 넣을려는 값이 큐에 있는지 확인하는 과정을 할 필요가 없었다는 것이다. 나는 원래 그래프 자체를 거쳤다는 것을 1로 표기를 하고 넘어갔는데, 1로 표기를 하는게 아니라 현재 단계에서 높이(익은 일자)가 어떻게 되는지 현재값+1을 그래프에 새겨놓음으로써 그래프 자체에 현재 토마토가 언제 익었는지 확인하는 방법을 넣어두는 것이다..
처음엔 이 부분이 너무 이해가 안되서 애초에 디큐가 자동으로 중복을 제거하나 싶었는데 또 그건 아니었고, 논리 흐름을 곰곰히 생각해보니 그래프에 값이 0이면 삽입을 하는데 애초에 지나가면서 그래프에 토마토가 익힌 일자를 표기하니까 이미 지난 것은 0일리가 없는 것이었다.
from collections import deque
import sys
input=sys.stdin.readline
dx = [0,0,1,-1]
dy = [1,-1,0,0]
graph = []
day = 0
q = deque([])
M,N = map(int, input().split())
for i in range(N):
graph.append(list(map(int, input().split())))
for i in range(N):
for j in range(M):
if(graph[i][j] == 1):
q.append([i,j])
while q:
cur = q.popleft()
# 상하좌우 판단
for i in range(4):
x = cur[0] + dx[i]
y = cur[1] + dy[i]
# 크기 안에서 & 0인 값 & 큐에 없는 값
if( (0<= x <= N-1 and 0<= y<= M-1) and graph[x][y] == 0):
q.append([x,y])
graph[x][y] = graph[cur[0]][cur[1]] + 1
for i in (graph):
for j in i:
if(day < j) : day = j
if(j == 0):
print(-1)
exit(0)
print(day - 1)!!!파이썬에서는 a=b는 깊은 복사다!!!
그렇다..파이썬은 a = b 를 할 때 a 자체가 b랑 완전 같은 변수로 a를 바꾸면 b가 b를 바꾸면 a가 바뀌게 된다..이를 간과하고 코드를 막 짜니 당연히 제대로 되지 않을 수 밖에..
코드를 수정하고 나니 토마토가 -1에 갇혀지지 않은 경우들에서 정답과 일치하는 횟수를 얻을 수 있었다.
graph = []
queue = []
M,N = map(int, input().split())
for i in range(N):
graph.append(list(map(int, input().split())))
for i in range(N):
for j in range(M):
if(graph[i][j] == 1):
queue.append([i,j])
day = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
temp_queue = []
# 큐를 2개 만들어서 하나는 소비용, 하나는 다음꺼 저장용
while(any(0 in l for l in graph)):
day += 1
while queue:
cur = queue.pop()
# 상하좌우 판단
for i in range(4):
x = cur[0] + dx[i]
y = cur[1] + dy[i]
# 크기 안에서 & 0인 값 & 큐에 없는 값
if( (0<= x <= N-1 and 0<= y<= M-1) and graph[x][y] == 0 and [x,y] not in queue):
temp_queue.append([x,y])
graph[x][y] = 1
queue = temp_queue[:]
print(graph, day)[S1]2667] 단지 번호 붙이기
😥 시도 1 : 실패
아이디어 자체는 연결된 것을 보고 차근 차근 접근하는 BFS방식으로 해결을 하려고했다.
구현하는 것 자체는 무식하게 구현을 했는데 사실 이렇게 하는게 맞으려나 싶긴 하면서 이렇게 하면 정답 자체는 구해질 것이라고 확신했다. 아무튼 구현 자체도 조금 오래 걸리긴 했지만 무언가 원하던 값이 아니라 자꾸 어디선가 단지 값들이 잘못 더해지는 부분이 있어서 그 부분을 확인하려고 print로 디버깅을 찍어보는데 시간이 소요됐다.
고민을 하고 print로 찍어보니 내가 이미 방문했는지 여부만 확인했지, 이미 큐에 들어가 있는 것에 대해서는 생각을 못했다..그 부분에 대해 수정하고 다시 돌려봐야겠다.
visited = []
q = []
record = [0] * 100
def search(a, b, idx):
q.append([a,b])
while(q):
# 큐에서 빼내자
cur = q.pop(0)
# 1이면서 아직 방문 안했으면!
if([cur[0],cur[1]] not in visited):
# 연결요소들 방문하고 현재꺼는 방문했다고 남기자
visited.append([cur[0],cur[1]])
#하측
if(cur[0]+1 <= n-1 and graph[cur[0]+1][cur[1]] == 1 and [cur[0]+1,cur[1]] not in visited):
q.append([cur[0]+1,cur[1]])
record[idx] = record[idx] + 1
print('하',cur[0]+1,cur[1])
#상측
if(cur[0]-1 >= 0 and graph[cur[0]-1][cur[1]] == 1 and [cur[0]-1,cur[1]] not in visited):
q.append([cur[0]-1,cur[1]])
record[idx] = record[idx] + 1
print('상',cur[0]-1,cur[1])
#우측
if(cur[1]+1 <= n-1 and graph[cur[0]][cur[1]+1] == 1 and [cur[0],cur[1]+1] not in visited):
q.append([cur[0],cur[1]+1])
record[idx] = record[idx] + 1
print('우',cur[0],cur[1]+1)
#좌측
if(cur[1]-1 >= 0 and graph[cur[0]][cur[1]-1] == 1 and [cur[0],cur[1]-1] not in visited):
q.append([cur[0],cur[1]-1])
record[idx] = record[idx] + 1
print('좌' ,cur[0],cur[1]-1)
n = int(input())
count = 0
graph = []
for i in range(n):
graph.append(list(map(int, input())))
for i in range(n):
for j in range(n):
# 1이면서 방문체크가 안되있는 경우 실행
if([i,j] not in visited and graph[i][j] == 1):
print('------------------------')
search(i,j, count)
print(record[count])
print('------------------------')
count+=1
print(count)
for i in record:
if(i >= 1): print(i)😥 시도 2 : 실패
코드랑 조건이 너무 길고 복잡하다보니 조금씩 코드가 잘못 들어간 부분이 너무 많았다..해당 부분을 수정하느라 많은 시간이 소요됐다. 시간이 걸리더라도 차분히 문제에 접근하고 풀어나갈 필요가 있다
3789가 나왔는데 3%까지 검사가 되다가 틀렸다 왜 틀린걸까..이해가 되지 않는다.
visited = []
q = []
record = [0] * 100
def search(a, b, idx):
q.append([a,b])
record[idx] = record[idx] + 1
while(q):
# 큐에서 빼내자
cur = q.pop(0)
# 1이면서 아직 방문 안했으면!
if([cur[0],cur[1]] not in visited):
# 연결요소들 방문하고 현재꺼는 방문했다고 남기자
visited.append([cur[0],cur[1]])
#하측
if(cur[0]+1 <= n-1 and graph[cur[0]+1][cur[1]] == 1 and [cur[0]+1,cur[1]] not in visited and [cur[0]+1,cur[1]] not in q):
q.append([cur[0]+1,cur[1]])
record[idx] = record[idx] + 1
#상측
if(cur[0]-1 >= 0 and graph[cur[0]-1][cur[1]] == 1 and [cur[0]-1,cur[1]] not in visited and [cur[0]-1,cur[1]] not in q):
q.append([cur[0]-1,cur[1]])
record[idx] = record[idx] + 1
#우측
if(cur[1]+1 <= n-1 and graph[cur[0]][cur[1]+1] == 1 and [cur[0],cur[1]+1] not in visited and [cur[0],cur[1]+1] not in q):
q.append([cur[0],cur[1]+1])
record[idx] = record[idx] + 1
#좌측
if(cur[1]-1 >= 0 and graph[cur[0]][cur[1]-1] == 1 and [cur[0],cur[1]-1] not in visited and [cur[0],cur[1]-1] not in q):
q.append([cur[0],cur[1]-1])
record[idx] = record[idx] + 1
n = int(input())
count = 0
graph = []
for i in range(n):
graph.append(list(map(int, input())))
for i in range(n):
for j in range(n):
# 1이면서 방문체크가 안되있는 경우 실행
if([i,j] not in visited and graph[i][j] == 1):
print('------------------------')
search(i,j, count)
print(record[count])
print('------------------------')
count+=1
print(count)
for i in record:
if(i >= 1): print(i)🥰 시도 3 : 성공!!!!!!!!!!!!!!!!
아무리 봐도 논리적으로 잘못된 것이 없었고, 한참을 이해가 되지 않았다..일단 내가 만든 코드 자체가 너무 길고 쓸데없이 복잡하긴 했는데 큰 틀은 비슷하게 푸는 것이 맞다고 생각했고 고민을 하던 끝에 도저히 몰라 서칭을 하다 ⭐오 름 차 순⭐ 안한 것을 알았다. 문제 자체가 도시가 7 8 9 로 순차적으로 나와서 그렇지 애초에 정렬을 하는 과정이 필요했다..이런 부분을 제대로 해결하지도 않았으니 당연히 틀렸다고 나올 수 밖에..
어디 찾아보고 진행한 것이 아니라 혼자만의 힘으로 거의 해결 끝까지 왔지만 오름차순으로 인해 해결 못한 것이 조금 아쉽다..
visited = []
q = []
record = []
def search(a, b, idx):
q.append([a,b]) # 접근한 인덱스 저장 [i][j]
record[idx] = record[idx] + 1
while(q):
# 큐에서 빼내자
cur = q.pop(0)
# 1이면서 아직 방문 안했으면!
if([cur[0],cur[1]] not in visited):
#현재꺼 방문했다고 남기자
visited.append([cur[0],cur[1]])
# 연결 요소들 방문
# (배열 범위 & 값 1 & 방문여부 & 큐에 있나 여부)
#하측
if(cur[0]+1 <= n-1 and graph[cur[0]+1][cur[1]] == 1 and [cur[0]+1,cur[1]] not in visited and [cur[0]+1,cur[1]] not in q):
q.append([cur[0]+1,cur[1]])
record[idx] = record[idx] + 1
#상측
if(cur[0]-1 >= 0 and graph[cur[0]-1][cur[1]] == 1 and [cur[0]-1,cur[1]] not in visited and [cur[0]-1,cur[1]] not in q):
q.append([cur[0]-1,cur[1]])
record[idx] = record[idx] + 1
#우측
if(cur[1]+1 <= n-1 and graph[cur[0]][cur[1]+1] == 1 and [cur[0],cur[1]+1] not in visited and [cur[0],cur[1]+1] not in q):
q.append([cur[0],cur[1]+1])
record[idx] = record[idx] + 1
#좌측
if(cur[1]-1 >= 0 and graph[cur[0]][cur[1]-1] == 1 and [cur[0],cur[1]-1] not in visited and [cur[0],cur[1]-1] not in q):
q.append([cur[0],cur[1]-1])
record[idx] = record[idx] + 1
n = int(input())
count = 0
# 2차원 배열 생성
graph = []
for i in range(n):
graph.append(list(map(int, input())))
for i in range(n):
for j in range(n):
# 1이면서 방문체크가 안되있는 경우 실행
if([i,j] not in visited and graph[i][j] == 1):
record.append(0)
search(i,j, count)
count+=1 # 단지 갯수 파악
print(count) # 총 단지 개수
record.sort()
for i in record:
if(i >= 1): print(i) # 각 단지 내 집의 수🚨개선점
내 코드가 너무 지저분해서 다른 대체법이 분명히 존재할거라 생각했다.
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
이런 식으로 구성한다면 반복문을 통해서 4칸 모두가 접근이 가능하다..
for i in range(4):
graph[dx + x][dy + y]
[G4]1707] 이분 그래프
[G5]13549] 숨바꼭질 3
시도 1: 런타임 에러?
인덱스 크기도 10만으로 잡았는데 계속 런타임 에러:인덱스 오류가 발생했다..뭔가 너무 이상해서 값을 임의로 계속 넣어보니 111,10000을 넣었을 때 visited[select]쪽이 터졌다..
import sys
from collections import deque
input=sys.stdin.readline
# 큐에 넣기
# 반복 : cur == target 될떄까지
def bfs():
q = deque()
q.append([start,0])
visited = [0] * 100001
while(True):
qq = q.popleft()
q_value = qq[0]
q_cnt = qq[1]
# 큐 뽑은 거 연산
for select in (q_value-1, q_value+1, q_value*2):
# 종료조건
if(select == target):
return q_cnt+1
# 방문여부 확인 후 큐에 넣자
if(visited[select] == 0):
visited[select] = 1
if(select == q_value*2):
q.append([select,q_cnt])
else:
q.append([select,q_cnt+1])
start, target = map(int, input().split())
print(bfs())
시도 2 : 틀렸습니다.
select 값 자체가 너무 크게 넘어가는 것을 막기 위해 조건을 걸어준 후로 정상적으로 됬긴 했는데 정답이 아니었다.
import sys
from collections import deque
input=sys.stdin.readline
def bfs():
q = deque()
q.append([start,0])
visited = [0] * 10000000 #방문여부체크 배열
while(True):
qq = q.popleft()
q_value = qq[0] #큐에서 뽑은 값
q_cnt = qq[1] #큐에 횟수
# 큐 뽑은 거 연산
for select in (q_value-1, q_value+1, q_value*2):
# 종료조건
if(select == target):
return q_cnt+1
# 방문여부 확인 후 큐에 넣자
if(select <= 100000 and visited[select] == 0):
visited[select] = 1
if(select == q_value*2):
q.append([select,q_cnt])
else:
q.append([select,q_cnt+1])
start, target = map(int, input().split())
print(bfs())
시도 3:
이리저리 고친 것은 많은데 가장 생각하지 못한 건 appendleft이다..왜 그냥 큐에 붙이지 않고 left를 해야할까 싶었는데 애초에 우린 최소의 횟수로 이동을 해야하고 최소의 횟수라면 2를 활용하는 것이 가장 먼저 우선으로 될 것이다..근데 머리로는 이해가 되기는 하는데 그렇다면 2가 우선순위가 될 수 없는 경우도 있지 않을까 하는 생각도 들었지만 애초에 *2로 해결할 수 없다면 +1이나 -1을 통해서 다른 방법으로 접근을 하긴 했을 것이다..
조금 더 고민하고 생각을 하자
import sys
from collections import deque
input=sys.stdin.readline
MAX = 1000001
def bfs():
q = deque()
q.append(start)
visited = [0] * MAX #방문여부체크 배열
visited[start] = 1
while(True):
q_value = q.popleft()
if(q_value == target):
print(visited[q_value] -1 )
return
# 큐 뽑은 거 연산
for select in (q_value-1, q_value+1, q_value*2):
# 방문여부 확인 후 큐에 넣자
if(0 <= select <= MAX-1 and visited[select] == 0):
if(select == q_value*2):
visited[select] = visited[q_value]
q.appendleft(select)
else:
visited[select] = visited[q_value] + 1
q.append(select)
start, target = map(int, input().split())
bfs()[S1]1325] 효율적인 해킹
시도 1: 시간초과
딕셔너리를 통해 문제를 해결하려 하였다. 딕셔너리에 키에 값이 존재하는 경우에는 append 아닌 경우는 dic[key] = value로 배정을 하려고 했는데 잘 안되서 서칭을 해서 찾아보았다.
해당 key가 딕셔너리에 존재하는지 확인하는 방법은 if key in graph: 를 사용해서 키가 그래프 안에 존재하는지를 확인하는 방법이 있었다. 해당 부분을 넘어가고는 큰 막힘없이 진행하였다가 정렬을 해서 큰 수부터 출력을 해야하는데 해당 방법이 마땅히 떠오르지 않았다.
그래서 그냥 배열에 있는 최대 값을 찾아놓고 배열을 순회하면서 해당 값을 찾으면 그 인덱스를 출력하는 방식으로 진행하였으나, 시간초과로 실패했다.
import sys
input=sys.stdin.readline
n,m = map(int,input().split())
graph = {}
for _ in range(m):
A, B = map(int, input().split())
if B in graph:
graph[B].append(A)
else:
graph[B] = [A]
hacking = []
for i in graph:
cnt = 0
q = [i]
while(q):
key = q.pop()
if(key in graph):
q.extend(graph[key])
cnt+=1
hacking.append(cnt)
# 정렬을 하는데 어떻게 원래 위치를 기억할까..
# 최대 크기를 알아놓고 배열을 순회하면서 돌자!
max = max(hacking)
cnt = 0
for i in hacking:
cnt +=1
if(i == max): print(cnt, end=' ')[G5]17086] 아기 상어 2 ←???
시도 1 : 틀렸습니다
지금까지의 BFS는 1을 발견하고 다음 1들을 찾으러 갔다면 이번엔 0을 찾고 뻗어나가서 1을 찾으면 되는 문제였고 문제를 푸는데 크게 어려운 것은 없었다. 예시도 정답에 이르렀고 제출을 했다. 하지만 28% 검사에서 틀렸다는 메시지가 떴다..
def bfs(a, b):
#현재꺼 큐에 넣고 상하좌우 대각에 있는 게 있다면 연결 ㄱ
q = []
q.append([a,b])
cnt = 0
while(q):
cur = q.pop()
for i in range(8):
x = dx[i] + cur[0]
y = dy[i] + cur[1]
if(0 <= x <= row-1 and 0 <= y <= col-1 and cage[x][y] == 1 ):
return cnt
if(0 <= x <= row-1 and 0 <= y <= col-1 and cage[x][y] == 0):
q.append([x,y])
cage[x][y] += cage[cur[0]][cur[1]] + 1
cnt += 1
row, col = map(int,input().split())
cage = []
dx = [0,0,1,-1,-1,-1,1,1]
dy = [1,-1,0,0,-1,1,-1,1]
for i in range(row):
cage.append(list(map(int,input().split())))
count = []
for i in range(row):
for j in range(col):
if(cage[i][j] == 1):
count.append(bfs(i,j))
print(max(count) + 1)
시도 2
5 4
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1왜 28%에서 잘 되지 않을까..이해가 잘 되지 않았고, 예시들을 만들어보기로 했다. 서칭해도 나처럼 28%에서 멈추는 분들이 있지 않길래 간단한 예시들을 만들면서 테스트 하던 중에 해당 경우는 분명 2보다 커야하는데 2라고 나오고 끝나서 이상함을 감지했다.
한참 이상한 것들을 하던 중 이해를 했다..애초에 코드에 논리가 틀린 것도 많았지만 가장 큰 문제는 문제 논리 자체를 이해 못했다..모든 칸에 대해 안전 거리를 구하는 문제지 아기상어간의 안전거리를 구하는 문제가 아니었다..
코드수정
def bfs(a, b):
q = []
q.append([a,b])
temp_q = []
cnt = 0
while(1):
while(q):
cur = q.pop()
print('시작 : ', cur)
for i in range(8):
x = dx[i] + cur[0]
y = dy[i] + cur[1]
if(a==x and b==y):
continue
else:
if(0 <= x <= row-1 and 0 <= y <= col-1 and cage[x][y] == 0 ):
temp_q.append([x,y])
if(0 <= x <= row-1 and 0 <= y <= col-1 and cage[x][y] == 1):
print('끝 : ', x,y)
return cnt
q = temp_q[:]
cnt += 1
print('끝')
row, col = map(int,input().split())
cage = []
dx = [0,0,1,-1,-1,-1,1,1]
dy = [1,-1,0,0,-1,1,-1,1]
for i in range(row):
cage.append(list(map(int,input().split())))
count = []
for i in range(row):
for j in range(col):
if(cage[i][j] == 0):
count.append(bfs(i,j))
print(count)
print(max(count) + 1)
81%까지 가서 매우 기뻐했는데 메모리 초과가 나버렸다..
애초에 배열을 하나 더 만들어서 복사를 하는 것을 생각할 때부터 메모리가 비효율적이라곤 생각했는데 512M정도면 괜찮겠다 생각하고 넘긴게 문제였다..
시도 3 : 횟수 저장 배열 count 삭제 (메모리 초과)
import sys
input=sys.stdin.readline
def bfs(a, b):
q = []
q.append([a,b])
temp_q = []
cnt = 0
while(1):
while(q):
cur = q.pop()
for i in range(8):
x = dx[i] + cur[0]
y = dy[i] + cur[1]
if(a==x and b==y):
continue
else:
if(0 <= x <= row-1 and 0 <= y <= col-1 and cage[x][y] == 0 ):
temp_q.append([x,y])
if(0 <= x <= row-1 and 0 <= y <= col-1 and cage[x][y] == 1):
return cnt
q = temp_q[:]
cnt += 1
row, col = map(int,input().split())
cage = []
dx = [0,0,1,-1,-1,-1,1,1]
dy = [1,-1,0,0,-1,1,-1,1]
for i in range(row):
cage.append(list(map(int,input().split())))
m_max = 0
temp = 0
for i in range(row):
for j in range(col):
if(cage[i][j] == 0):
temp = bfs(i,j)
if(m_max < temp): m_max = temp
print(m_max + 1)
수많은 시도를 거친 후..
정말 지긋지긋한 문제였다...이루 블로그에 적을 수 없을만큼 수많은 착오를 거쳤고 사실 아직 이게 왜 정답인지 잘 모르겠다..처음엔 메모리가 초과되는 것이 문제가 되어 그것을 막기 위해서 큐에 x,y값과 함께 현재 횟수를 더하는 방식을 추가했고 그 다음엔 visited를 만들어 붙인 후부터 계속 틀렸다고 나오고 풀수록 내가 뭘 틀린건지 솔직하게 몰랐다..
그러던 중 코드의 최적화나 해볼까 하는 생각에 일반 큐를 디큐로 바꿨는데 정답이 됐다..뭐지 pop이나 popleft나 큐에 있는 것들을 끄집어 낸다는 동작은 똑같을텐데 pop은 뒤에 있는 것을 끄집어내긴 한다만 뒤에서 끄집어 내든 앞에서 끄집어 내던 넣은 큐들을 순차적으로 끄집어내면 안되는 거 아닌가 싶었는데
이해 : 큐에는 지금 시작하는 case[a][b] == 0 인 곳에서부터 대각 좌우상하를 보고 1인 곳을 찾기까지 0들을 모두 큐에 삽입하고 다시 큐를 보고 대각 상하좌우를 보는데, 넣은 순서에 맞게 순차적으로 끄집어내야지 그렇게 하지 않고 뒤에서부터 끄집어낸다면 순서가 뒤죽박죽이 되어 올바르게 끝나지 않을 것이다.
[S2]4963] 섬의 개수
😆 시도 1: 맞았습니다ㅏ!!!!!!!!!!!!!
처음으로 DFS,BFS문제에서 한 번에 아이디어, 한 번의 시도로 정답에 도달할 수 있었다..기쁨과 성취가 느껴지고 한 번에 맞았다는게 무언가 행복하기도 하면서 재미있었다.
아이디어는 이전 BFS를 풀 듯이 진행했다. 이 전에 아이디어들을 잘 구현할 수 있나 없나와 세세한 출력해야하는 것들의 차이를 구현하는 것들이 필요했다.
지도에 1로 표시된 정보들을 순회하면서 연결여부를 파악하고, 이미 연결했다면 정보를 표시하는 것까지 해두었다.
잘하고있다 더 노력하자!
row = 1
col = 1
map_inf = []
dx = [0,0,1,-1,-1,-1,1,1]
dy = [1,-1,0,0,-1,1,-1,1]
def bfs(a, b):
#현재꺼 큐에 넣고 상하좌우 대각에 있는 게 있다면 연결 ㄱ
q = []
q.append([a,b])
while(q):
cur = q.pop()
for i in range(8):
x = dx[i] + cur[0]
y = dy[i] + cur[1]
if(0 <= x <= col-1 and 0 <= y <= row-1 and map_inf[x][y] == 1):
q.append([x,y])
map_inf[x][y] += map_inf[cur[0]][cur[1]] + 1
while(row + col != 0):
row,col = map(int,input().split())
cnt = 0
if(row + col == 0):break
map_inf = []
# 지도 정보 받기
for i in range(col):
map_inf.append(list(map(int,input().split())))
# 이어져있는 섬을 파악하자.
# 반복문으로 전체 돌고 1로 되어있다면 큐에 넣고 다음으로
for k in range(col):
for j in range(row):
if(map_inf[k][j] == 1):
bfs(k,j)
cnt+=1
print(cnt)