백준 2468
이전에 풀었던 아이스크림 만들기 문제처럼, 코드를 작성하였다.
import sys
N = int(sys.stdin.readline())
height = []
x = 0
while x < N :
input = list(map(int,sys.stdin.readline().split()))
height.append(input)
x= x+1
maxval = max(map(max,height))
def dfs(x,y,rain) :
cango[x][y] = True
if x < 0 or x >= N or y < 0 or y >= N:
return False
if (cango[x][y] == False) and (height[x][y] > rain) :
cango[x][y] = True
#그 점은 지나갔습니다.
dfs(x+1,y,rain)
dfs(x,y+1,rain)
dfs(x,y-1,rain)
dfs(x-1,y,rain)
return True
#다 돌아봣는데 색칠안할것이 없음
elif (cango[x][y] == False) and (height[x][y] <= rain) :
cango[x][y] = True
return False
#그점은, height가 낮아서 세지는 않지만 지나갔음 .
return False
maxcount = 0
for i in range(maxval) :
cango = [[False] * (N) for _ in range(N)]
count = 0
for j in range(N) :
for z in range(N) :
if dfs(j,z,i) == True :
count = count +1
if maxcount < count :
maxcount = count
print(maxcount)
DFS 에서 문제가 발생했다.
1. 저번 경우에는 모든곳으로 뻗어가는 조건이 동일했는데, 이번에는 상하좌우로 뻗을때마다 확인이 필요하다.
2. 이러한 문제의 경우에는 DFS에서 N의 범위를 벗어나지 않게 설정해줘야하는데, 이 설정이
HEIGHT를 어긋나서 DFS가 중지되었을때랑 같아문제가 발생했다.
import sys
N = int(sys.stdin.readline())
sys.setrecursionlimit(100000)
height = []
x = 0
while x < N:
insert = list(map(int, sys.stdin.readline().split()))
height.append(insert)
x = x + 1
def dfs(x, y, rain):
if x < 0 or x >= N or y < 0 or y >= N:
return False
if cango[x][y] == False and height[x][y] > rain:
cango[x][y] = True
# 그 점은 지나갔습니다.
dfs(x + 1, y, rain)
dfs(x, y + 1, rain)
dfs(x, y - 1, rain)
dfs(x - 1, y, rain)
return True
# 다 돌아봤는데 색칠 안할 것이 없음
else:
return False
maxcount = 0
for z in range(1, max(map(max, height)) + 1):
cango = [[False] * N for _ in range(N)]
count = 0
for i in range(N):
for j in range(N):
if cango[i][j] == False and height[i][j] > z:
dfs(i, j, z)
count = count + 1
if maxcount < count:
maxcount = count
print(maxcount)
70 %에서 오류 발생.. 반례를 찾는게 굉장히 어렵다.
import sys
N = int(sys.stdin.readline())
sys.setrecursionlimit(100000)
height = []
x = 0
while x < N:
insert = list(map(int, sys.stdin.readline().split()))
height.append(insert)
x = x + 1
def dfs(x, y, rain):
if x < 0 or x >= N or y < 0 or y >= N:
return False
if cango[x][y] == False and height[x][y] > rain:
cango[x][y] = True
# 그 점은 지나갔습니다.
dfs(x + 1, y, rain)
dfs(x, y + 1, rain)
dfs(x, y - 1, rain)
dfs(x - 1, y, rain)
return True
# 다 돌아봤는데 색칠 안할 것이 없음
else:
return False
maxcount = 0
for z in range(max(map(max, height))):
cango = [[False] * N for _ in range(N)]
count = 0
for i in range(N):
for j in range(N):
if cango[i][j] == False and height[i][j] > z:
dfs(i, j, z)
count = count + 1
if maxcount < count:
maxcount = count
print(maxcount)
# 찾았다 . . . . .
문제는 바로 for z .
만약에 최대 높이가 최대 숫자라면, 다 잠기기 때문에 의미가 없다.
혹은 최대 높이가 0이라면 , 모든것이 잠기지 않는다.
반례를 찾았다.
2
1 1
1 1
원래는 비가 안올 수도 있으니 1이 나와야하지만,
1부터 시작하면 0이 나온다
이러한 인접한 node들의 조건을 찾을때는
1. 범위를 벗어나면 재귀 중단
2. dfs함수를 사용할때도 재귀에서 true로 탐색한 조건과 맞을때만 dfs를 호출해야한다.
(둘 중 한개만 맞을때 dfs를 호출하면, 큰 case로 보았을때는 틀릴 수 있다. )
3. 방문했다고 무조건 true로 바꾸면 안된다.
왜냐하면 true로 바꿨기 때문에 인접 노드가 조건에 맞음에도 불구하고 이동하지 못할 수 있기 때문.
이전 dfs bfs 문제들은 지금 node는 갔고, 다음 node에 대한 질문을 진행했는데
이번 문제는 지금 node를 확인하고, 지금 node에 대한 질문을 진행하기 때문에
node가 무조건 갔다고 취급해서는 안되는것 !
백준 2667
import sys
N= int(sys.stdin.readline())
graph = []
forloop = 0
while forloop < N :
graph.append(list(map(int,sys.stdin.readline().strip())))
forloop = forloop +1
dx = [-1,1,0,0]
dy = [0,0,-1,1]
#갔는지 안갔는지는 , 0 으로 확인합시다.
def DFS(x,y,count) :
graph[x][y] = 0
for i in range(4) :
nx = x+dx[i]
ny = y+dy[i]
if 0<=nx<N and 0 <= ny < N and graph[nx][ny] == 1:
count = DFS(nx,ny,count+1)
return count
answerarr = []
cnt= 0
for i in range(0,N) :
for j in range(0,N) :
if graph[i][j] == 1:
cnt = cnt+1
answerarr.append(DFS(i,j,1))
print(cnt)
for i in sorted(answerarr) :
print(i)
혼자서 풀어냈고, 주의해야 할 부분을 정리하겠다.
1. 101111이 출력될때 [1,0,~~~]로 받고 싶으면
list(map(int,sys.stdin.readline().strip())으로 받아야한다. split으로 받으면 띄어쓰기가 없어서 한번에 받아진다. 주의 .
2. count로 return을받고 , 해당 count +1로 재 호출한다
즉 a -> b-> c-> d 호출하게되면 어렵게 생각하지말고 count가 1개씩 커지는 값이 들어가다보면, 최종적으로 끝날때의 count가 위 레벨로 돌아가고 돌아가고 돌아간다 .
즉 1->2->3->4(매개변수 count입력)4->4->4->4로 (count) 복귀완료!
그냥 간단하게,
셀값 = dfs(셀 값)
return 셀 값으로 기억하자.
