오늘은 백준 문제 중 1325번 효율적인 해킹 문제를 해결해보았다. 해당 문제는 한번의 해킹으로 최대한 많은 컴퓨터를 해킹하기를 원한다. 각 컴퓨터는 신뢰 관계가 있는데 만약 신용 받는 컴퓨터를 해킹하면 신용하는 컴퓨터는 자동으로 해킹이 된다.
해당 문제의 특징은 그래프가 일반 그래프가 아니라는 점과 한번에 가장 많은 수의 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 리턴해주어야 한다는 특징이 있다.
from collections import deque
n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
for _ in range(m):
x, y = map(int, input().split())
adj[y].append(x)
def bfs(v):
q = deque([v])
visited = [False] * (n+1)
visited[v] = True
count = 1
while q:
v = q.popleft()
for e in adj[v]:
if not visited[e]:
q.append(e)
visited[e] = True
count += 1
return count
result = []
max_value = -1
for i in range(1, n+1):
c = bfs(i)
if c > max_value:
result = [i]
max_value = c
elif c == max_value:
result.append(i)
max_value = c
for e in result:
print(e, end=" ")
db 연결은 LINQ to SQL 클래스를 사용했고 해당 부분은 동영상을 참조하면 될 것이다.
이글에서는 GRID를 사용하기 위해서 Controller 단과 클라이언트 html 파일 위주로 정리하겠다.
public class WM_BILLOFMATERIAL_CONTROLLER : ApiController
{
private Data.NorthwindContextDataContext _context = new Data.NorthwindContextDataContext();
HttpRequest _request = HttpContext.Current.Request;
public Models.Response Get()
{
int take = _request["take"] == null ? 10 : int.Parse(_request["take"]);
int skip = _request["skip"] == null ? 0 : int.Parse(_request["skip"]);
var bom = (from b in _context.WM_BILLOFMATERIAL
select new Models.WM_BILLOFMATERIAL(b)).Skip(skip).Take(take).ToArray();
return new Models.Response(bom, _context.WM_BILLOFMATERIAL.Count());
}
public HttpResponseMessage Post()
{
var response = new HttpResponseMessage();
try
{
var bom_update = (from bom in _context.WM_BILLOFMATERIAL
where bom.ITEMID == _request["ITEMID"]
select bom).FirstOrDefault();
if (bom_update != null)
{
bom_update.QTY = _request["QTY"] == null ? bom_update.QTY : Convert.ToDecimal(_request["QTY"]);
_context.SubmitChanges();
}
else
{
response.StatusCode = System.Net.HttpStatusCode.InternalServerError;
response.Content = new StringContent(string.Format("the Item with itemId {0} was not found in the database"));
}
return response;
}catch (Exception ex)
{
response.StatusCode = System.Net.HttpStatusCode.InternalServerError;
response.Content = new StringContent(string.Format("there was an error updating bom"));
return response;
}
}
}
위 컨트롤러에는 Get 메서드와 Post 메서드가 있다.
해당 메소드들을 통해 Get 요청과 Post 요청을 처리한다.
뭔가 매핑을 하지않아도 메서드 이름을 Get, Post로 정한 다음에 사용하기만 해도 처리가 된다.
Controller가 수행되는 순서에 대해 정리해보겠다.
클라이언트에서 Controller로 get, post 등의 요청을 하면 제일 먼저 클래스 가장 위의 Data.NorthwindContextDataContext _context가 가장 먼저 실행되고 다음으로
HttpRequest _request = HttpContext.Current.Request 가 실행되었다.
해당 변수들은 생성자에 들어가있지도 않은데 디버깅 포인트가 해당 포인트에서 가장 먼저 잡히는 것이 이해가 잘 안 되었다. 그래서 NorthwindContextDataContext를 Ctrl + 우클릭으로 타고 들어가 보니 mapping이란 키워드가 들어간 변수가 있었다. 아마 자동으로 매핑해주기 위해서 생성된 클래스 같다.
다음 순서로 URL 경로가 맞다면 해당 요청에 해당되는 POST 또는 GET 메소드가 실행된다.
GET 메소드의 경우 아래와 같이 구현되어있다. 우선 핵심인 LINQ가 사용된 부분을 보자면
in 뒤에있는뒤에 있는 클래스들 통해 값을 받고 from 뒤에 있는 변수 이름에 값을 넣고 select를 통해서 값을 표현할 방식을 정한다. 그다음 take과 skip은 kendo grid에서 갑을 한 번에 얼마나 가지고 올지를 정하는 부분이다. 그리고 데이터를 성공적으로 가져왔다면 Models 클래스에 있는 Response에 해당 값을 담아서 클라이언트로 반환을 해준다. 아래 코드를 통해 말하자면 한 페이지에 10개의 행을 나타내겠다는 의미이다.
public Models.Response Get()
{
int take = _request["take"] == null ? 10 : int.Parse(_request["take"]);
int skip = _request["skip"] == null ? 0 : int.Parse(_request["skip"]);
var bom = (from b in _context.WM_BILLOFMATERIAL
select new Models.WM_BILLOFMATERIAL(b)).Skip(skip).Take(take).ToArray();
return new Models.Response(bom, _context.WM_BILLOFMATERIAL.Count());
}
다음으로 Post 메소드를 살펴보겠다. Post 메서드는 아래와 같이 구현되어있다.
public HttpResponseMessage Post()
{
var response = new HttpResponseMessage();
try
{
var bom_update = (from bom in _context.WM_BILLOFMATERIAL
where bom.ITEMID == _request["ITEMID"]
select bom).FirstOrDefault();
if (bom_update != null)
{
bom_update.QTY = _request["QTY"] == null ? bom_update.QTY : Convert.ToDecimal(_request["QTY"]);
_context.SubmitChanges();
}
else
{
response.StatusCode = System.Net.HttpStatusCode.InternalServerError;
response.Content = new StringContent(string.Format("the Item with itemId {0} was not found in the database"));
}
return response;
}catch (Exception ex)
{
response.StatusCode = System.Net.HttpStatusCode.InternalServerError;
response.Content = new StringContent(string.Format("there was an error updating bom"));
return response;
}
}
위 포스트 메서드는 사용자가 웹 화면에서 특정 아이템의 재고량을 변화시킬 때 사용되는 메서드이다. 사용자가 특정 아이템의 재고량을 수정하고 업데이트 버튼을 클릭하면 수행된다. 사용자가 입력한 값이 만약에 null이라면 업데이트하지 않도록 하거나 에러가 발생하게 되면 처리해주는 로직이 추가되어 있다.
다음으로 Default.aspx를 살펴보겠다. 해당 파일은 사용자가 사용할 UI 단 웹이다. 해당 파일 중 script 부분을
집중적으로 분석해보겠다.
<script>
$(function () {
$("#employeesGrid").kendoGrid({
columns: [
{ field: "ITEMID", title: "아이템ID" },
{ field: "QTY", title: "수량" },
"ISVALID",
{ command: ["edit", "destroy"], title: ""}
],
sortable: true,
pageable: true,
// editable: true,
editable: "inline",
dataSource: new kendo.data.DataSource({
transport: {
read: "api/WM_BILLOFMATERIAL_",
update: {
url: function (WM_BILLOFMATERIAL) {
//return "api/WM_BILLOFMATERIAL_/" + WM_BILLOFMATERIAL.ITEMID
return "api/WM_BILLOFMATERIAL_/" + WM_BILLOFMATERIAL.ITEMID
},
type: "POST"
}
},
pageSize: 15,
serverPaging: true,
schema: {
// the array of repeating data elements (employees)
data: "Data",
// the total count of records in the whole dataset. used
// for paging
total: "Count",
model: {
id: "ITEMID",
fields: {
ITEMID: { editable: false , nullable: false },
QTY: { validation: { required: true }, nullable: false },
ISVALID: { validation: { required: true }, nullable: false }
}
}
}
})
});
});
</script>
위 스크립트 태그 안에 있는 내용은 전부 하나의 kendoGrid를 위한 기능이다. 해당 함수의 기능을 위에서부터 아래로 살펴보도록 하겠다.
columns
가장 위에 있는 columns에는 columns 이름 그대로 kendoGrid에서 나타나게 될 속성들의 모임이다. 만약에 속성 이름 그대로 안 쓰고 다른 이름을 쓰고 싶다면 { filed: "ITEMID", title: "아이템 ID" }라고 쓰면 되고 속성 이름을 변경 없이 그대로 사용하고 싶으면 "ISVALID" 그냥 속성 이름을 문자열 형태로 주면 된다.
sortable
위 sotable 변수에 true 값을 넣어주게 되면 속성 이름을 클릭할 수 있게 되는데 클릭을 하면 해당 속성 값을 기준으로 그리드의 행들이 정렬 되게 된다.
pageable
그리드의 모든 속성을 보여주지 않고 한 페이지에 해당되는 행의 수만큼 표현해서 보여주는 설정을 할 수 있도록 한다.
editable
편집을 가능하게 한다. true나 혹은 inline 값을 할당할 수 있었는데 true를 넣게 되면 속성 개별로 값을 할당할 수 있고 inline 값을 넣으면 한 행씩 편집할 수 있도록 한다.
import sys
sys.setrecursionlimit(100000)
def dfs(x,y):
visited[x][y] = True
directions = [(-1,0),(1,0), (0,-1), (0,1)]
for dx, dy in directions:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if array[nx][ny] and not visited[nx][ny]:
dfs(nx,ny)
for _ in range(int(input())):
m, n, k = map(int, input().split())
array = [[0] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]
for _ in range(k):
y, x = map(int, input().split())
array[x][y] = 1
result = 0
for i in range(n):
for j in range(m):
if array[i][j] and not visited[i][j]:
dfs(i, j)
result += 1
print(result)
위 코드를 활용해 답을 구하였다. 재밌는 점은 directions 리스트의 하나의 값에 x와 y 좌표를 담아 두었다. 그리고 for문을 돌면서 x,y좌표에 값을 더해서 돌도록 만들엇고 값의 범위가 올바른지 그리고 방문하지 않았던 좌표인지 그리고 벌레가 방문 할 수 있는 좌표인지 검증을 통해 dfs함수를 다시 호출한다. 해당 문제를 풀면서 dfs문제의 핵심이라 해도 될 정도로 중요한 문제라고 느꼈고 가끔식 복습해야겠다
main 메소드가 있는 곳에 @EnableJPaAuditing 어노테이션을 추가해주면 행을 추가할 때마다 @CreatedDate 이 있는 속성 의 값이 자동으로 들어가고 @LastModifiedDate 어노테이션이 있는 속성에는 update시점의 시간을 자동으로 기록하게 된다.
해당 문제는 간단해 보였지만 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 하라는 조건 때문에 응근히 까다롭게 느껴졌다.
n, m, v = map(int, input().split())
graph1 = {}
visited = list()
visited_dfs = list()
need_visited = list()
need_visited.append(v)
need_visited_dfs = list()
need_visited_dfs.append(v)
for _ in range(m):
key, value = map(int, input().split())
if key in graph1:
graph1[key].append(value)
else:
graph1[key] = [value]
while need_visited:
vertex = need_visited.pop(0)
if vertex not in visited:
visited.append(vertex)
if vertex in graph1:
need_visited.extend(graph1[vertex])
while need_visited_dfs:
vertex = need_visited_dfs.pop()
if vertex not in visited_dfs:
visited_dfs.append(vertex)
if vertex in graph1:
need_visited_dfs.extend(graph1[vertex])
print(visited)
print(visited_dfs)
위 코드가 처음에 작성한 코드였다. 정점 번호가 작은걸 우선 방문하라는 조건을 빼면 일반 DFS, BFS 기능은 나온 것 같다. 작은걸 우선 방문하라는 조건을 지키기 위해서는 DFS와 BFS의 정렬 순서가 역정렬이 되어야 조건을 충족시킬 수 있을 것으로 보인다.
아래 코드가 답코드이다.
from collections import deque
def dfs(v):
print(v, end= ' ')
visited[v] = True
for e in adj[v]:
if not(visited[e]):
dfs(e)
def bfs(v):
q = deque([v])
while q:
v = q.popleft()
if not(visited[v]):
visited[v] = True
print(v, end=' ')
for e in adj[v]:
if not visited[e]:
q.append(e)
n, m, v = map(int, input().split())
adj = [[] for _ in range(n+1)]
for _ in range(m):
x, y = map(int, input().split())
adj[x].append(y)
adj[y].append(x)
for e in adj:
e.sort()
visited = [False] * (n + 1)
dfs(v)
print()
visited = [False] * (n + 1)
bfs(v)
deque를 사용하는 이유는 그냥 list를 사용하는거 보다 성능상 유리한 면이 있어서인 것 같다.
